Section 9 Chapter 53 - The Turing Machine
No description yet. This curated deck is ready for daily study.
Card preview (7)
Structure of a Turing Machine
An infinitely long strip of tape, divided into squares, along with a read-write head that is controlled by a finite state machine
What is a turing machine in terms of what it computes
It can be seen as a computer with a single fixed program
Features of a turing machine (4)
• 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
Structure of the states in a Turing Machine
One start state and one or more halting states
Syntax for a transition function
δ(Current State, Input) = (Next State, Output, Movement)
Universal Turing Machine
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.
Important of the Turing machine
Provides a formal model of computation and provide a definition for what is computable