The function TuringMachine generates a list that represents the evolution of a Turing Machine given a rule that specifies its behaviour (i.e. set of instructions).

For example, the following rule specifies a 2-color, 2-state Turing Machine:

rule = {
       {0, 1} -> {0, 1, -1},
       {0, 0} -> {0, 0, 1}

More general, rules are of the form:

{state, cell color} -> {new state, new color, head movement}

We can then get the evolution of this Turing Machine (for 20 steps) in state 1 on a tape filled with 0':

TuringMachine[rule, {1, {{}, 0}}, 20]

Do you have an idea how I can specify a halting state? Or how to identify when a Turing Machine has halted within t steps?

  • $\begingroup$ Welcome to Mathematica.SE! 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour and check the faqs! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Jan 2 '17 at 18:57
  • $\begingroup$ Strange, the documentation doesn't seem to mention anything about halting. And halting is a fairly important property of Turing machines. What if you defined rules so that each of your "halting states" did not change the state of the machine? And you wrote a little function that would look at the output from TuringMachine for the first instance where a step did not change the state and that told you when it halted. $\endgroup$ – Bill Jan 2 '17 at 19:56
  • $\begingroup$ Many thanks for the idea! I'll try this approach and let you know how it went. I thought that there might be another way of doing this not mentioned on the documentation. $\endgroup$ – Lili Jan 2 '17 at 19:57
  • 1
    $\begingroup$ Sometimes MMA functions are written in MMA and you can find the source code buried down in the MMA folders, often this is hinted at when the details of the documentation say you have to use << or Get before using the function. But this seems rare now and I didn't find the source for TuringMachine. Sometimes details are just left out of the documentation until someone points it out. $\endgroup$ – Bill Jan 2 '17 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.