Cognitive Scaffold

Preparing your thinking workspace

arrow_back_ios_new
MENTAL MODEL · M5708

Gap Theorem

Gap Theorem
TechnicalHigh supportComputer Science
Included
account_tree

Updated 2026-08-05

Loading revision record…

INTRODUCTION

English translation pending.

CORE DEFINITION

Proved by Boris Trakhtenbrot and independently by Allan Borodin, the gap theorem shows that for any resource measure such as time or space there exist arbitrarily large gaps in which increasing the resource bound does not enlarge the class of functions computable within it. The construction exploits the way resource bounds interact with machine encodings rather than any property of real hardware. The core claim is that resource and capability are not continuously related. The qualification is that the result is asymptotic and does not predict the behavior of practical systems.

SCAFFOLDING EFFECT

psychology

Reduce cognitive load

- Use Gain Verification: Check whether added resources actually expanded capability before assuming they did. - Use Step Change Search: Look for the magnitude of increase that crosses a gap rather than incremental top-ups. - Use Gap Awareness: Expect that some expansions produce no new capability at all.

anchor

Anchor fast decisions

Computability within a bound depends on whether a machine can complete its work before the limit is reached, and the relationship between the bound and the achievable class is not smooth. There are ranges where every machine that fits the smaller bound also fits the larger one, so the larger budget adds nothing. Capability therefore increases in steps with gaps between them rather than rising continuously with resources.

MINIMUM ACTION

In progress 0/1

Practice this model in one real situation:

Check to track your progress (stored locally)
Learning progress0%
account_treeGenealogyexpand_more
menu_bookReferencesexpand_more

Source support: Explicit

  • link
    zh.wikipedia.orghttps://zh.wikipedia.org/wiki/%E9%96%93%E9%9A%99%E5%AE%9A%E7%90%86ZH · Explicit
    verified

RELATED MODELS

Related model

Zero-Knowledge Proof

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true. Thus, it can be understood as a 'zero-leakage proof'.

arrow_forwardRelated model

Batching

A batch file is a script file in DOS, OS/2, and Microsoft Windows, used as a scripting language to run programs. It is a text file containing a series of commands to be read and executed by an interpreter with a command-line interface. It is applied in DOS and Windows systems, interpreted and run by the built-in interpreter (usually COMMAND.COM or CMD.EXE). It is equivalent to a shell script in Unix-like systems. In DOS and Windows 9x operating system families, the file extension for batch files is .bat. In OS/2 and Windows NT families, the .cmd extension is added. In other operating systems, batch files may have different extensions, for example, 4OS, 4OS2, and 4NT use the .btm extension. When a batch file is executed, the shell program reads the file content and then executes its commands, typically line by line.

arrow_forwardRelated model

Head-of-Line Blocking

Head-of-line blocking (HOL blocking) is a performance-limiting phenomenon in computer networking. It occurs when the first packet in a queue (the head) is blocked, causing the entire queue of packets to be blocked. This can happen in switches with buffered inputs, due to out-of-order transmission, or in HTTP pipelining with multiple requests.

arrow_forward