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*