Church-Turing Thesis

Turing Machine

A Turing Machine is a 7 tuple

• is finite set of states
• is finite input alphabet
• is finite tape alphabet

A configuration consists of (1) content of tape in (2) state in (3) position of head . The initial configuration is

If machine reaches or , it halts. Define to be

A Turing machine accepts if there is a sequence of configurations where is the start configuration of to , yields , and is an accepting configuration.

Turing Recognizable

is Turing recognizable or recursively enumerable if such that

It is Turing decidable or recursive if such that when halts on accept, and means halts on reject.

Variants

Multitape Turing Machine

Nondeterministic Turing Machine

These are both equivalent to regular Turing machines

An enumerator is a Turing-machine that has a working tape, along with a printer tape. A language is Turing-recognizable iff some enumerator enumerates it.

Church-Turing Thesis

Any physically realizable computational device can be simulated by standard Turing machine up to polynomial time loss in efficiency.