To use a Turing machine as a Transducer, treat the entire nonblank
portion of the initial tape as input, and treat the entire nonblank portion
of the tape when the machine halts as output.
11. When is a function f said to be “Turing computable”?
A Turing machine defines a function y f x
= ( ) for strings x y
,
*
∈ Σ if
q x q y
f
0 |–
*
where q f is the final state.
A function f is ‘Turing Computable” if there exists a Turing machine
that can perform the above task.
12. When are two automata said to be equivalent?
Two automata are said to be equivalent if they accept the same
language.
13. When are two transducers said to be equivalent?
Two transducers are said to be equivalent if they compute the same
function.
14. What do you mean by standard Turing machines?
At each move of a Turing machine, the tape head may move either
left or right. We can augment this with a ‘stay’ option, i.e. we will add
“don’t move” to the set {L, R}.
Turing machines with a stay option are equivalent to Standard
Turing Machines.
15. What is an N-Track Turing machine?
A TM in which each square of the tape holds an ordered n-tuple of
symbols from the tape alphabet is said to be an N-Track Turing
Machine.
16. What is a semi-infinite tape Turing Machine?
A Turing machine having a semi-infinite tape, with the non-blank
input at the extreme left of the tape is called so.
17. What is an offline Turing machine?
A Turing machine having two tapes, one tape being read-only and
has the input, the other being read-write that is initially blank is called an
offline Turing machine.
18. What is a multi-tape Turing machine?
A Turing machine with finite number of tapes, each having its own
independently controlled tape head is called a multi-tape TM.
19. What are standard Turing Machines?
Multi-tape Turing machines are called standard Turing Machines.
20. What is a binary Turing Machine?
A Turing machine whose tape alphabet having exactly two symbols
is a binary Turing Machine.
208
Theory of Automata, Formal Languages and Computation
portion of the initial tape as input, and treat the entire nonblank portion
of the tape when the machine halts as output.
11. When is a function f said to be “Turing computable”?
A Turing machine defines a function y f x
= ( ) for strings x y
,
*
∈ Σ if
q x q y
f
0 |–
*
where q f is the final state.
A function f is ‘Turing Computable” if there exists a Turing machine
that can perform the above task.
12. When are two automata said to be equivalent?
Two automata are said to be equivalent if they accept the same
language.
13. When are two transducers said to be equivalent?
Two transducers are said to be equivalent if they compute the same
function.
14. What do you mean by standard Turing machines?
At each move of a Turing machine, the tape head may move either
left or right. We can augment this with a ‘stay’ option, i.e. we will add
“don’t move” to the set {L, R}.
Turing machines with a stay option are equivalent to Standard
Turing Machines.
15. What is an N-Track Turing machine?
A TM in which each square of the tape holds an ordered n-tuple of
symbols from the tape alphabet is said to be an N-Track Turing
Machine.
16. What is a semi-infinite tape Turing Machine?
A Turing machine having a semi-infinite tape, with the non-blank
input at the extreme left of the tape is called so.
17. What is an offline Turing machine?
A Turing machine having two tapes, one tape being read-only and
has the input, the other being read-write that is initially blank is called an
offline Turing machine.
18. What is a multi-tape Turing machine?
A Turing machine with finite number of tapes, each having its own
independently controlled tape head is called a multi-tape TM.
19. What are standard Turing Machines?
Multi-tape Turing machines are called standard Turing Machines.
20. What is a binary Turing Machine?
A Turing machine whose tape alphabet having exactly two symbols
is a binary Turing Machine.
208
Theory of Automata, Formal Languages and Computation