0
$\begingroup$

Have a question that requires me to write the rules for parsing a turing machine

This is the question

The PROBLEM involves writing a set of Turing Machine rules that will read and determine whether or not an input corresponds to the rules of a Turing Machine. This is the first step of a Universal Turing Machine. For example, if the input is a legal set of rules, then the machine shall accept this input (and any other legal input that describes a Turing Machine).

The input would be IO = current state with the number of I's indicating what state I = would be the current symbol being true with O being false IIO = next state I = next symbol with O being false I or O = direction with I being left and O being right

so a legal input would be

IOOIIOOI which would be state 1 = current state false = next state 2 = next state false = left

How would I write the rule so that if I ran it through and it detected that the rules did not conform to the legal input it would place II at the beginning of the input and if its correct put OO at the beginning.

$\endgroup$
  • 2
    $\begingroup$ have you written any code before? is this homework? $\endgroup$ – vzn Apr 6 '14 at 15:21
  • $\begingroup$ I have written code before and I'm stuck at the implementation of it, I have only done very basic Turing machines like adding and read to end of instructions, and I'm unsure where to start this one $\endgroup$ – Sam Apr 6 '14 at 20:53
  • $\begingroup$ write 2 or 3 TM instructions as they should appear on the input tape of the TM that is supposed to read them. Then try to imagine how you would check that they are correctly written.... $\endgroup$ – babou Apr 8 '14 at 13:13

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.