Chapter 19 - The Turing Machine Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is the Turing machine?

A

A theoretical model of computation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define Alphabet

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the Read/Write head?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the Halting state?

A

The state that stops the Turing machine.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the Start state?

A

The initial state of a Turing machine.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the Transition function/rule?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define Instruction table.

A

A method of describing a Turing machine in tabular form.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define Universal machine

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Key Points:

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly