Turing Machines
#computer-science #computational-thinking #turing-machines
Turing Machiens
A Turing machine is a theoretical device thought of by Allan Turing in
1936 which can carry out any computer algorithm, no matter how
complex.
What is a Turing Machine?
A Turing machine is an FSM which can read or write data (a string of
characters) to any position on an infinitely long tape according to a set of
rules.
A Turing machine has:
A finite set of states
A finite alphabet of symbols
An infinite tape with marked off squares
A sensing read-write head that can travel along the tape one square at a
time
The machine must have a start state and at least one stop state -- the
halting state
Any alphabet of symbols may be used, but we generally use only a binary
alphabet of 0 and 1 and _ for a blank square
The controller is a Finite State Machine which tells the machine what to do
next.
In any one transition, the machine can:
Read the symbol on the tape
, Erase or write a new symbol
Move the head left or right by a single space
Turing Machines can be described as Mealy Machines with a third output --
a direction.
Input/Output, Direction
Transition Function
The function that defines the transitions between states
A way to represent the transition arc
Can be represented with δ notation
δ(Current State, Input State) = {Next State, Output Symbol, Head Move}
Importance of Turing Machines
Turing Machines act as a definition of what is and is not computable. It
is proven that a Turing Machine is capable of computing any algorithm.
Complex algorithms can be constructed by combining simple Turing
Machines that each solve a part of the problem.
Universal Turing Machine
A Universal Turing Machine (UTM) can simulate any TM by first reading a
description of all the TMs required to solve a problem, and then the input
required for the calculations.
Repeatability
It will faithfully execute operations on the data precisely as the TM being
simulated does.
All modern computers are based on the idea of the Turing Machine -- they
take a program and act on the input, performing logical operations to give an
, output
#computer-science #computational-thinking #turing-machines
Turing Machiens
A Turing machine is a theoretical device thought of by Allan Turing in
1936 which can carry out any computer algorithm, no matter how
complex.
What is a Turing Machine?
A Turing machine is an FSM which can read or write data (a string of
characters) to any position on an infinitely long tape according to a set of
rules.
A Turing machine has:
A finite set of states
A finite alphabet of symbols
An infinite tape with marked off squares
A sensing read-write head that can travel along the tape one square at a
time
The machine must have a start state and at least one stop state -- the
halting state
Any alphabet of symbols may be used, but we generally use only a binary
alphabet of 0 and 1 and _ for a blank square
The controller is a Finite State Machine which tells the machine what to do
next.
In any one transition, the machine can:
Read the symbol on the tape
, Erase or write a new symbol
Move the head left or right by a single space
Turing Machines can be described as Mealy Machines with a third output --
a direction.
Input/Output, Direction
Transition Function
The function that defines the transitions between states
A way to represent the transition arc
Can be represented with δ notation
δ(Current State, Input State) = {Next State, Output Symbol, Head Move}
Importance of Turing Machines
Turing Machines act as a definition of what is and is not computable. It
is proven that a Turing Machine is capable of computing any algorithm.
Complex algorithms can be constructed by combining simple Turing
Machines that each solve a part of the problem.
Universal Turing Machine
A Universal Turing Machine (UTM) can simulate any TM by first reading a
description of all the TMs required to solve a problem, and then the input
required for the calculations.
Repeatability
It will faithfully execute operations on the data precisely as the TM being
simulated does.
All modern computers are based on the idea of the Turing Machine -- they
take a program and act on the input, performing logical operations to give an
, output
