Chapter 19 - The Turing Machine

Question 1

What is the Turing machine?

Answer 1

A theoretical model of computation.

Question 2

Define Alphabet

Answer 2

The acceptable symbols (characters, numbers) for a given Turing machine.

Question 3

What is the Read/Write head?

Answer 3

The theoretical device that writes or reads from the current call of tape in a Turing machine.

Question 4

What is the Halting state?

Answer 4

The state that stops the Turing machine.

Question 5

What is the Start state?

Answer 5

The initial state of a Turing machine.

Question 6

What is the Transition function/rule?

Answer 6

A method of noting how a Turing machine moves from one state to another and how the data on the tape changes.

Question 7

Define Instruction table.

Answer 7

A method of describing a Turing machine in tabular form.

Question 8

Define Universal machine

Answer 8

A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape

Question 9

Key Points:

Answer 9

• The Turing Machine is able to carry out any algorithm and in doing so essentially produces a model of what is computable. It works with a tape of an infinite length split into cells.
• Each cell has a value in it, typically a 0,1 or a blank but could have any symbols.
• The read/write head can move in any direction along the entire length of the tape.