Section 9 Chapter 53 - The Turing Machine

Question 1

Structure of a Turing Machine

Answer 1

An infinitely long strip of tape, divided into squares, along with a read-write head that is controlled by a finite state machine

Question 2

What is a turing machine in terms of what it computes

Answer 2

It can be seen as a computer with a single fixed program

Question 3

Features of a turing machine (4)

Answer 3

• A finite set of states in a state transition diagram
• A finite alphabet of symbols
• An infinite tape with marked-off squares
• A read-write head which can travel up and down the tape

Question 4

Structure of the states in a Turing Machine

Answer 4

One start state and one or more halting states

Question 5

Syntax for a transition function

Answer 5

δ(Current State, Input) = (Next State, Output, Movement)

Question 6

Universal Turing Machine

Answer 6

A machine that can take the description of any Turing machine and the data. The machine will then act on the data in the exact same way as the turing machine that was described to it would.

Question 7

Important of the Turing machine

Answer 7

Provides a formal model of computation and provide a definition for what is computable