28 Nov 2012
School
Department
Course
Professor
An algorithm for effectively calculating a number-theoretic function is a
procedure that
a) can be specified in a finite number of steps
b) can be unambiguously followed by a human or mechanical
computer
c) will always yield an output for any input for which the function is
defined
(…)
Turing machine: Summary
- Idealized computing machines that can be specified purely
mathematically
- Do not have to take any particular physical form
- The machine table of a Turing machine is the program, specifying
what the appropriate output for a given input.
How it works
- Infinitely long tape divided into individual cells
- A finite alphabet of symbols, of which there must be exactly one in
each cell.
- A scanner/printer that can read what is in a given cell and write in it.
- The machine table of the Turing machine specifies instructions for
the scanner/printer.
- When the scanner/printer is in a given state it can
Move one cell to the L/R
Erase what is in a cell
Write a new symbol at a state
(…)
- The very same set of functions is calculable, however these
particulars are settled.
- The instructions specify what action to carry out given a) the internal
state of the machine, b) the input
- Each instruction has the same form Q*p, S*j, A, Q*t
Q*p – Internal state (…)
(…)
Sample program: example
Q1
0
R
Q*
2
Q2
1
0
Q*
1
Q3
0
1
Q*
3
Q4
1
R
Q*