{:check ["true"], :rank ["computability" "universal_turing_machine" "undecidability"]}
Let a function
be a function over strings. We say that a Turing Machine
Given a string
,
Initialize the tape with
. If
is defined, then the TM will halt in an accepting state, and the final tape content must be exactly followed by blanks.
Decision problem:
Let
. We call such function predicates because they
only return one bit: true or false, for any given input.
Computable functions:
If a function
has a TM implementation, then we call computable.
Decidable functions:
If
is a predicate and computable, we call decidable.
An important theorem: the Church-Turing Thesis
Modern day computers are equivalent to Turing Machine in the sense that:
Every computable function has an algorithm.
Every algorithm implements some computable function.
Given some algorithm
- Each different algorithm will require its own TM.
- In order to have different algorithms, we will need to build infinitely many different TM each with its own distinct control logic.
The profound genius of Alan Turing:
Simulation of TM is computable.
Turing Machines can simulate Turing Machines.
Let's define simulation
Simulation is computable.
UTM is the only TM we ever need to build.
If we want to build a TM
+----------+---------------------
| logic(M) |
+----------+---------------------
Whenever we need to execute
+----------+----------+----------
| logic(M) | input(M) |
+----------+----------+----------
Now, we can start executing the universal TM
+-----------+--------------------
| output(M) |
+-----------+--------------------
Programming
Given an algorithm
Compilation
The control logic of
Runtime execution
During the execution of the universal TM, the tape is divided to
two regions:
Remember how computation started?
Entscheidungsproblem
If a problem can be described formally in mathematical logic, can it always be decided by mechanical reasoning?
TM settles the entscheidungsproblem with a negative answer.
The Accepting Problem
Given a TM
and an initial content of its tape, will accept ? We defin the function:
Undecidability of the Accepting Problem
Theorem:
There does not exist a TM that implements the function
.
The proof is by contradition. Let assume that
Let's consider
We can construct another computable function:
Let's try to evaluate
Does
Does
Conclusion:
The function
cannot possible be a program.