Theory of Computation208110 marksNumerical: Turing machine encodingEncoding of Turing Machine
Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q0, q1, q2}, {a, b}, {a, b, B}, δ, q2, B, F) with input w = ba and δ is defined as follows: δ(q0, b) → (q1, b, R), δ(q1, a) → (q2, a, R), δ(q2, a) → (q1, a, R), δ(q2, b) → (q2, b, L)
Define Turing machine as enumerators of strings of a language. Encode the Turing machine TM = ({q0, q1, q2}, {a, b}, {a, b, B}, δ, q2, B, F) with input w = ba and δ is defined as follows: δ(q0, b) → (q1, b, R), δ(q1, a) → (q2, a, R), δ(q2, a) → (q1, a, R), δ(q2, b) → (q2, b, L)[10]
A Turing machine used as an enumerator is a variant of the standard TM equipped with a work tape and a separate output tape (printer). Instead of taking an input and accepting/rejecting it, an enumerator $E$ starts on a blank tape and generates (lists) the strings of a language. - $E$ starts with...