Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limits to Computation - Coggle Diagram
Limits to Computation
Hard Problems
In theoretical computer science, a problem is considered hard if the best-known algorithm has a high running time.
-
Definition of Hard Algorithms:
Runs in exponential time, O(c^n) for some constant c > 1.
-
-
-
Impossible Problems
The Halting Problem states that it is impossible to write a program that can determine, for any arbitrary program and input, whether the program will eventually halt or continue indefinitely (enter an infinite loop)
Uncountability
If every member of a set can be mapped to a positive integer, the set is countable.
Countability of Programs
Programs are represented as strings of characters (including special characters, spaces, line breaks).
The set of all possible programs is countable because strings can be assigned to bins by their length and character composition
Implications
The uncountability of integer functions implies that not all functions can be implemented as computer programs.
This is a foundational result in computability theory, highlighting the limitations of what can be computed by algorithms
-
-