Homework SourseConsider the following Turing machine 3a Write all 7 compone
Consider the following Turing machine:
3a. Write all 7 components of the formal description of this TM.
3b. Write out the sequence of con?gurations this TM goes through on each of the following inputs: 000, 001, 010, 100.
3c. Argue why this TM decides a language, and say what language it decides.
3d. Show that the language decided by this TM is actually regular.
Solution
Following Hopcroft and Ullman (1979, p. 148), a (one-tape) computing device are often formally outlined as a 7-tuple alphabetic character,\\Gamma ,b,\\Sigma ,\\delta ,q_,F\ angle } M=\\langle letter of the alphabet,\\Gamma ,b,\\Sigma ,\\delta ,q_,F\ angle wherever
{\\displaystyle letter of the alphabet} Q could be a finite, non-empty set of states
\\Gamma could be a finite, non-empty set of tape alphabet symbols
b\\in \\Gamma is that the blank image (the solely image allowed to occur on the tape infinitely typically at any step throughout the computation)
} \\Sigma \\subseteq \\Gamma \\setminus \\ is that the set of input symbols
} \\delta :(Q\\setminus F)\\times \\Gamma \ ightarrow Q\\times \\Gamma \\times \\ could be a partial perform referred to as the transition perform, wherever L is left shift, R is true shift. (A comparatively uncommon variant permits \"no shift\", say N, as a 3rd part of the latter set.) If \\delta isn\'t outlined on this state and also the current tape image, then the machine halts.[21]
{\\displaystyle q_\\in letter of the alphabet} q_\\in Q is that the initial state
{\\displaystyle F\\subseteq letter of the alphabet} F\\subseteq Q is that the set of ultimate or acceptive states. The initial tape contents is alleged to be accepted by M if it eventually halts during a state from F.
Anything that operates in keeping with these specifications could be a computing device.
The 7-tuple for the 3-state busy beaver sounds like this (see additional regarding this busy beaver at computing device examples):
},},},}\\}} Q=\\},},},}\\}
} \\Gamma =\\
b=0 (\"blank\")
} \\Sigma =\\
{\\displaystyle q_=}} q_=} (the initial state)
{\\displaystyle F=\\{}\\}} F=\\{}\\}
\\delta = see state-table below
Initially all tape cells area unit marked with .
