Turing machines
State 1: If you scan 0, flip it to 1, switch to state 2, and move right. Else, switch to state 3 and move left. State 2: If you scan 0, flip it to 1, switch to state 1, and move left. Else, move right. State 3: If you scan 0, flip it to 1, switch to state 2, and move left. Else, stop. Here I will use [ ] to denote the machine. It starts like ...00000[0]00000... in state 1. It then goes to ...000001[0]0000... and then 00000[1]10000... Now it goes to state 3 with ...0000[0]110000... It eventually reaches ...00111[1]11000... in state 3, after which it stops. For 3-state machines that eventually halt, this takes the longest time to halt, taking 21 steps. How do we know whether a Turing machine will ever halt? We can simulate it for long enough. If it halts, good. If not, it might halt or it might not. But can a Turing machine (or a computer) tell whether another Turing machine halts? Turing proved that the answer is no. The only way to prove whether it halts is for a human to examine it on a case-by-case basis. This may be extremely diffcult at times but it is sometimes very easy for humans (but impossible for computers). An example is a Turing machine that moves left if it scans 0 and halts otherwise. This Turing machine will, on a tape with only 0s, go left forever and never halt. A human could prove that. Many other simple Turing machines can be proven not to halt. However, a computer could never prove it in the general case. Turing machines come in various forms. Your PC can simulate a Turing
machine. S and K combinators (from combinatory logic) can simulate a Turing machine. Conway's Life
can simulate a Turing machine. Ian Stewart proposed an innovative scenario
where a model train set can simulate a Turing machine (and, therefore,
your PC, S and K combinators, and Conway's Life). However, these things
may be extremely slow and would lack all input and output except the initial
configuration as input and the final position as output. Your PC is much
faster and more user-friendly than a Turing machine.However, any calculation
or program your PC can run, all of the others can too and get the right
result. Related entries Life Combinatory logic | ||
Home • Contact |