PHIL 3440

Turing Machine

For bonus reading:

See the Stanford Encyclopedia of Philosophy on-line.

1. Alonzo Church and Alan Turing conjectured that there is a class of effective or mechanical methods in mathematics and logic.

A method is effectively decidable, iff

· M is set out in terms of a finite number of exact instructions (each instruction being expressed by means of a finite number of symbols);

· M will, if carried out without error, produce the desired result in a finite number of steps;

· M can (in practice or in principle) be carried out by a human being unaided by any machinery save paper and pencil;

· M demands no insight or ingenuity on the part of the human being carrying it out.

(from B. Jack Copeland, 2002, "The Church-Turing Thesis," Stanford Encyclopedia of Philosophy, http://plato.stanford.edu/entries/church-turing/)

2. Turing showed that a simple sort of computer, a Turing machine, could carry out any effectively computable function.

3. The consequences for the philosophy of mind / cognitive science:

a. Any computation a human can perform unaided can be performed (again, in principle) by a simple computer.

b. If we could characterize human mental capacities as an effectively decidable procedure (or as a set of such procedures) a very simple computer could, given enough time and memory, carry them out.

4. Example Turing Machine:

A Turing Machine is characterized by a state, a tape divided into cells, a reader/writer/mover head, an instruction set, a location on the tape, the contents of the cells. Note that this is just one way to specify a Turing Machine - the exact construction is not important, for a Turing machine is abstractly specified.

Example function:

Addition:

(from Paul Ming’s Virtual Turing Machine website, located at:

http://www.nmia.com/~soki/turing/addition.html):

Semantics: a number is a series of ‘1’s including an extra ‘1’.

Instructions: (If in state s and cell contains t, go into state u, erase t and write v, then move)

Tape reads: B111011B

Initial State: Pass

Located at leftmost, nonblank character

pass, 1, pass, 1, R # get past the numbers

pass, 0, pass, 1, R # change the zero

pass, B, del1, B, L # end of second number, start going

# back to delete the last 1

del1, 1, del2, B, L # delete the last 1, go back to

# delete the second to last 1

del2, 1, stop, B, R # deletes the second to last 1

Of course this program works for any tape length.