turing machine
Table of Contents
Turing mahcine is a imaginary computation device with a inifinite long tape as memory and a head that can read from and write to the tape.
It has 4 primitives:
- move head 1 step left
- move head 1 step right
- read the charactor under head
- write a charactor to replace the charactor under head
Backlinks
turing complete
Any (imaginary) machine is turing complete if it can be used to simulate a turing machine, namely, implements the 4 primitives of turing machine.