Chapter 11 - Turing Machines

Question 1

What is a Turing Machine made up of?

Answer 1

A finite set of states (Q)
A finite set of symbols (the alphabet - also known as sigma)
A finite set of tape symbols such that the alphabet is a subset of tape symbols. (Written as a capital weird R)
A transition function
An initial state (Q0)
The blank symbol B, which is an element of the tape symbols
A set of final states (F)

Question 2

How does a Turing Machine accept a language?

Answer 2

The Turing Machine accepts a language by either going into an accepting state, or stopping in a non-accepting state if delta returns stop i.e. it never loops

Question 3

What does the format (Qx, character, direction) mean in regards to Turing Machines?

Answer 3

A Turing machine will use the state specified by Qx, and write the character, and finally rotate the tape in the specified direction.