Give a detailed description of a Turing Machine M which halts on every input and
ID: 3662077 • Letter: G
Question
Give a detailed description of a Turing Machine M which halts on every input and, when given a string x {0, 1}* , accepts if and only if there are strings y, z {0, 1}* and a non-negative integer n such that |y| = |z| = n and x = y1n z. Your Turing Machine must not alter any blank tape squares. That is, your machine is free to write over the contents of the tape containing the input, but it is not allowed to write any symbol to a blank tape square other than a blank symbol
(a) A detailed description of the tape alphabet (if you use any extra tape characters), giving the purpose of each extra character you introduce beyond and the blank character.
(b) A detailed description of the movement of the read-write head on an arbitrary input.
Explanation / Answer
Answer for 1:
Turing machines are an abstract model of computations. They Provide preciese, formal defination of what
it means for a function to be computable.
Key points:
1. A finite amount of internal state.
2.An finite amount of external data stroage.
3. A program specfied by a finite number of instructions in a predefined language.
following are Individual defined:
A Turing machine is a 7 tuple M =<Q,[,b,{,q0,s,F> we can define as
Q -- Is a finite ,non - empty set of states.
[ -- is a finite non empty set of the tape alphabet/symbols.
b belongs [, is the blank symbol.
q0 is the Intitial state.
{ subset of [ - {b} is the setof input symbols.
s :Q -F x [ ---> Q-F x [ x {L,R} is a partial function called the transition function. where L is the
left Shift, R is the right Shift.
Answer for 2:
a TM is a finite set of states Q, a semi finite tape that delimited on the left end by end marker
|- and is finite to the right. and head that canmove left and right over the tape, reading and writing
symbols.
The machine starts in its start state s with its head scanning the left endmarker. In each step it reads the symbol on the tape under its head. Depending on that symbol and the current state, it writes a new symbol
on that tape cell, moves its head either left or right one cell, and enters a new state. The action it takes
in each situation is determined by a transition function . It accepts its input by entering a special accept
state t and rejects by entering a special reject state r. On some inputs it may run infinitely without ever
accepting or rejecting, in which case it is said to loop on that input.
The input string of finite length and is intially written on the tape continously tape cells up against left end marker.
A Turing machine has an infinite one-dimensional tape divided into cells. Traditionally we think of the tape as being horizontal with the cells arranged in a left-right orientation. The tape has one end, at the left say, and stretches infinitely far to the right. Each cell is able to contain one symbol, either ‘0’ or ‘1’.
The machine has a read-write head which is scanning a single cell on the tape. This read-write head can move left and right along the tape to scan successive cells.
The action of a Turing machine is determined completely by
(1) the current state of the machine
(2) the symbol in the cell currently being scanned by the head and
(3) a table of transition rules, which serve as the “program” for the machine.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.