This particular result shows that any attempt to prove mathematics
consistent is foredoomed to failure. It is still possible to prove a system
consistent by logical arguments outside that system, provided the outer system
is known to be consistent.
6.2 RECURSIVE FUNCTION THEORY
It is seen that a sufficiently powerful formal system cannot be both consistent
and complete as proved by Godel. Simple arithmetic on integers is an example
of a system that is “sufficiently powerful”. It is always preferred to give up
completeness rather than consistency, because in a consistent system any
proposition can be proven.
Ideally, we wanted to have an algorithmic theorem proving procedure to
distinguish between the provable propositions and unprovable ones. Alan
Turing invented Turing machines in an attempt to solve this problem. With the
halting problem, Alan Turing had shown that it is not possible to distinguish
between soluable and insolvable problems. Similar results were arrived at by
other scientists. Church invented “Recursive Function Theory”.
6.3 PRIMITIVE RECURSIVE FUNCTIONS
This section describes the basic ideas behind recursive function theory.
The Recursive functions are described over the natural numbers I = {0, 1,
2, 3, ......}. Recursive functions are looked at as “Pure Symbol Systems”.
Numbers are not used in the system, rather, we use the system to construct both
numbers and arithmetical functions on numbers. Its a different numbering
system, in the same way as Roman numerals are different. The correspondence
is as given below.
z x
s z x
s s z x
( ) , ( ( )) , ( ( ( ))) , .....
=
=
=
0
1
2
In order to translate to decimal, just count the number of s’s surrounding
the central z(x).
(a) Zero Function: z x
z y
( )
( ),
=
for all x y I
,
.
∈ This is our “zero”; it is written
as a function so we don’t have to introduce constants into the system.
(b) Successor Function s(x): This function informally means x + 1. Formally,
it does not return a value. It just lies there, the result of s(x) is s(x).
(c) Projector Function:
p x
x
p x y x
p x y
y
1
1
2
( )
( , )
( , )
=
=
=
Computability
219
consistent is foredoomed to failure. It is still possible to prove a system
consistent by logical arguments outside that system, provided the outer system
is known to be consistent.
6.2 RECURSIVE FUNCTION THEORY
It is seen that a sufficiently powerful formal system cannot be both consistent
and complete as proved by Godel. Simple arithmetic on integers is an example
of a system that is “sufficiently powerful”. It is always preferred to give up
completeness rather than consistency, because in a consistent system any
proposition can be proven.
Ideally, we wanted to have an algorithmic theorem proving procedure to
distinguish between the provable propositions and unprovable ones. Alan
Turing invented Turing machines in an attempt to solve this problem. With the
halting problem, Alan Turing had shown that it is not possible to distinguish
between soluable and insolvable problems. Similar results were arrived at by
other scientists. Church invented “Recursive Function Theory”.
6.3 PRIMITIVE RECURSIVE FUNCTIONS
This section describes the basic ideas behind recursive function theory.
The Recursive functions are described over the natural numbers I = {0, 1,
2, 3, ......}. Recursive functions are looked at as “Pure Symbol Systems”.
Numbers are not used in the system, rather, we use the system to construct both
numbers and arithmetical functions on numbers. Its a different numbering
system, in the same way as Roman numerals are different. The correspondence
is as given below.
z x
s z x
s s z x
( ) , ( ( )) , ( ( ( ))) , .....
=
=
=
0
1
2
In order to translate to decimal, just count the number of s’s surrounding
the central z(x).
(a) Zero Function: z x
z y
( )
( ),
=
for all x y I
,
.
∈ This is our “zero”; it is written
as a function so we don’t have to introduce constants into the system.
(b) Successor Function s(x): This function informally means x + 1. Formally,
it does not return a value. It just lies there, the result of s(x) is s(x).
(c) Projector Function:
p x
x
p x y x
p x y
y
1
1
2
( )
( , )
( , )
=
=
=
Computability
219