Noam Chomsky
→ Unrestricted Grammars
Stephen Kleene
→ Recursive function Theory
Raymond Smullyn
→ Formal Systems.
All of the above formalisms were proved equivalent to one another. This
led to
(a) Turing’s Thesis (Weak Form): A Turing machine can compute
anything that can be computed by a general-purpose digital
computer.
(b) Turing’s Thesis (Strong Form): A Turing machine can compute
anything that can be computed.
The strong form of Turing’s Thesis cannot be proved it states a
relationship between mathematical concepts and the “real world”.
4.4.1 Counting
Two sets can be put into a one-to-one corresponding if and only if they have
exactly the same number of elements.
Example:
{red, yellow,
green,
blue}
{apple, banana, cucumber,
b
b
b
b
plum}
One-to-one correspondence with a subset of natural numbers can be done as:
{red, yellow, green, blue}
{1,
2,
3,
4}
↓
↓
↓
↓
4.4.2 Recur sive and Recur sively Enumerable Lan guage
There are three possible outcomes of executing a Turing machine over a given
input.
The Turing machine may
(i) Halt and accept the input
(ii) Halt and reject the input, or
(iii) Never halt.
A language is “recursive” if there exists a Turing machine that accepts
every string of language and rejects every string over the same alphabet that is
not in the language.
If a language L is recursive, then its complement L should also be
recursive.
Turing Machines
197