turing machine is a computational system that has a memory tape, and can go through the input multiple times; they don’t have to accept or reject states, turing machines can run forever and can have loops.
For the main topic, see turing machine
decidable vs. recognizable languages
- there are not enough Turing Machines to compute every language (so there are non-recognizable/non-decidable languages)
- halting problem and ATM, meaning strings where Turing Machines can’t decide them
- “the diagonalization argument”
- mapping reduction
- Rice’s Theorem
- strong reduction: higher achy of hard problems
self-reference
- turing Machines can view and produce its own code.
- foundations of mathematics can be shown using these systems
Kolomogorov Complexity
Non-deterministic Turing Machine
They are not really good computational system, non-determinism doesn’t add that much power by normal Turing Machine.
Encodeable Turing Machines
For every Turing Machine, we can encode it into a string. We can, for instance, use a turing machine to generate another turing machine.
This also allows us to make universal turing machines—using Turing machines to simulate anotherr turing machines.