Week 3 - Turing Machines: Introduction

Question 1

What are turing machines?

Answer 1

A model for devices/automata with unlimited memory, and unrestricted use of that memory. The define the theoretical limits of computation.

Question 2

What did M. Sipser say about Turing Machines?

Answer 2

A Turing Machine “can do everything that a real computer can do”.

Question 3

TRUE OR FALSE: Real computers are Turing Machines.

Answer 3

TRUE, though they are generally less powerful Turing machines.

Question 4

Decribe the internals of a Turing Machine in more detail.

Answer 4

A Machine with states, include and inital state and accepting state and rejecting state. It also has a memory (refered to as a tape) like the pushdown automata, but it is no a stack but memory that allows for any item in the memory to be accessed at any time. Imagine it like an infinite array. It accesses the memory through a ‘tape head’ which decides which item in memory it is looking at. The tape is initially filled with only the input string at the start of memory. A Turing machine will compute forever until it reaches either an accepting or rejecting state for the input.

Question 5

What is a tape head?

Answer 5

A index that specifies which item in memory that a Turing machine is accessing. It is used to read and write symbols on the memory.

Question 6

TRUE OR FALSE: The input alphabet for a Turing Machine can contain an empty symbol.

Answer 6

FALSE, because Turing machines need to use the empty symbol for empty memory, and thus it cannot be connected to a symbol in the alphabet.

Question 7

What are the main differences between Turing machines and the automata we have learned about so far?

Answer 7

The input string is stored in the tape (Memory).
It has unlimited, unrestricted memory.
It will continue forever, unless it reaches either the accept or reject state.

Question 8

What symbol is used to describe the tape?

Answer 8

Γ