Informally: Given sufficient data storage capacity and time, all computers (laptops, iPhones, super computers,...) can perform the same set of computations. In particular, they can perform numerical computations with any degree of precision required and, in particular, as Turing Machines
Definition :
A Turing Machine
consists of:
An alphabet
:
A finite set of symbols including
The tape: A 1 dimensional sequence of cells. Each cell is referenced by an Integer.
Each
cell can contains a single symbol from the
, all but a finite number of cells contain the blank symbol
.
At different stages of a Turing Machine computation, the tape will contain a different configuration of symbols.
A finite set of head states
.
An Initial state:
A halting state - Accept:
.
A halting state - Reject:
.
The read/write Head: In a given state
and
"positioned over" a given cell,
A single valued Transition Function:
of
valid steps.
Read
if the head is in state
and
it is over a cell containing symbol
and
change
the symbol in the present cell to
, change the head state to
,
and
move
eft
or
ight
one cell, or
ot
at all, depending on
.
It is common practice to write
rather than 
.
Notation:
denotes
that is in state
and
the tape contains the consecutive sequence of symbols
with
all blanks to the left of
and to the right of
.
Moreover the head is over the cell containing
.
We call this the state of
, as opposed to the head state.
Given
and valid step
we
write
More generally
will
be used to denote a sequence of valid steps refered to as a
derivation.
Alternate Definitions: There are many computationally equivalent definitions of Turing Machine..
One A: simple, in fact more commonly used, variation is as
above except in the Transition Function, rather than Head
,
only
are
available.
To create a computationally equivalent
for a given
Turing Machine
For
each add a new state
and
rules .
For every step of the form
replace
it with a step,
and
for each
a
rule
Two Another variant defines
.
Here, in a given step, either the cell under the Head gets rewritten or the
Head moves not both.
A Convenient 3-tape Turing Machine :
The input tape: A read-only tape containing the input, unidirectional in that its head can only move left to right;
The work tape: Where all computations are carried out, bidirectional but initially blank:
The output tape: unidirectional and Initially blank, where the result of the computation is copied from the working tape, before halting.
We say such a Turing Machine halts on
input 
with
output 
, and write
if
is to the left of the input head and
is to the left of the output head after
halts. .