Please enable JavaScript.
Coggle requires JavaScript to display documents.
Non-computability, fast-growing functions, etc. - Coggle Diagram
Non-computability, fast-growing functions, etc.
Busy Beaver
-
The Busy Beaver is a function BB(k), that when you input k it returns a value which is the max. steps it can take before halting
As you can see from the table to the left, BB(k) grows very very fast
-
-
Halting Problem explained by apps: Turing’s proof of undecidability of the Halting Problem explained in terms of phone apps
The Freeze app: tests a suspicious app and determines if it will freeze your phone (e.g. enter an infinite loop, or crashes/terminates) or not.
-
The Paradox app: if Paradox halts according to the freeze app, it will enter a loop and not halt. if Paradox doesn't halt according to the freeze app, it will halt.
This is impossible! How can Paradox app halt when it doesn't halt and doesn't halt when it halts? This doesn't make any sense.
-
If Freeze app exists, the Paradox app exists, but Paradox app doesn't exist so Freeze app can't exist (contradiction).
Reductions: Problem X reduces to Problem Y, if you can use an algorithm that solves Y to help solve X
-
-
Black boxes
Black box is a device, system or object which can be viewed in terms of its inputs and outputs, without any knowledge of its internal workings.
-
-
Oracles
An Oracle (in computability theory) is an abstract device, which can be viewed in terms of its inputs and outputs.
-
-
Halting Problem Program Vs. Oracle : Oracle theoretically exists but Program cannot exist,
Even programs that can call the Halting problem oracle, cannot solve the Halting Problem.
