Turing Machines

Question 1

What is a turing machine

Answer 1

• Model of computation which can describe all computers
• Different variations to describe a Turing machine
• Has an infinite ‘tape’ data structure

Question 2

What are the limitations of a turing machine

Answer 2

• UTM is hardwired
• Can only execute only one program
• But real computers are re-programmable

Question 3

What are the different components of a turing machine?

Answer 3

• Infinite Tape
  
  • Acts as memory
  • Each cells contains one symbol
• Read write head
  
  • Connected to CU
  • Can move from one location left or right
• State Register
  
  • Stores the state of the machine
• Finite table of instructions
  
  • Can erase or write a symbol
  • Move the head left, right or not at all
  • Go to new state or stay in the same state

Question 4

Describe the tape data structure

Answer 4

• Tape is divided into cells
  
  • Each cell contains on symbol
• Symbols can be from the alphabet and can be Σ ={0,1, a, b, x, $, etc}
• Δ (delta) = empty or blank cell
• Head can read, write and can move left or right one cell at a time

Question 5

Describe how a turing machine works

Answer 5

Question 6

Define a turing machine

Answer 6

Defined using 7 tuples