3.1 TURING MACHINES (Turing vélar)

Question 1

Turing machines were first proposed by who and when ?

Answer 1

Alan Turing in 1936

Question 2

Similar to a finite automaton but with an unlimited and unrestricted memory, a Turing machine is a much more accurate model of a

Answer 2

general purpose computer.

Question 3

How does the Turing machine work ?

Answer 3

The Turing machine model uses an infinite tape as its unlimited memory. It has a tape head that can read and write symbols and move around on the tape.

Initially the tape contains only the input string and is blank everywhere else. If the machine needs to store information, it may write this information on the tape. To read the information that it has written, the machine can move its head back over it. The machine continues computing until it decides to produce an output.

Question 4

Name four differences between finite automata and Turing machines

Answer 4

1. A Turing machine can both write on the tape and read from it.
2. The read–write head can move both to the left and to the right.
3. The tape is infinite.
4. The special states for rejecting and accepting take effect immediately.

Question 5

A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qaccept, qreject), where Q, Σ, Γ are all finite sets and

Answer 5

1. Q is the set of states,
2. Σ is the input alphabet not containing the blank symbol ␣, 3. Γ is the tape alphabet, where␣∈ Γ and Σ ⊆ Γ,
3. δ: Q×Γ−→Q×Γ×{L,R} is the transition function,
4. q0 ∈ Q is the start state,
5. qaccept ∈ Q is the accept state, and
6. qreject ∈ Q is the reject state, where qreject ̸= qaccept.

Question 6

What is configuration of the Turing machine?

Answer 6

As a Turing machine computes, changes occur in the current state, the current tape contents, and the current head location. A setting of these three items is called a configuration of the Turing machine.

Question 7

The collection of strings that M accepts is the language of M, or the language recognized by M, denoted L(M).

Question 8

Call a language Turing-recognizable if some Turing machine recognizes it.

Question 9

When we start a Turing machine on an input, three outcomes are possible. They are ?

Answer 9

The machine may accept, reject, or loop.

Question 10

By loop we mean ?

Answer 10

that the machine simply does not halt. Looping may entail any simple or complex behavior that never leads to a halting state.

Question 11

What are deciders?

Answer 11

Turing machines that halt on all inputs; such machines never loop.

Question 12

A decider that recognizes some language also is said to

Answer 12

decide that language.

Question 13

Call a language Turing-decidable or simply decidable if some Turing machine decides it.