- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Marchal <marchal.domain.name.hidden>

Date: Thu Oct 18 10:27:38 2001

To all victims of certainties.

Hi all,

Thanks for those who makes out-of-line comments of

Diagonalisation 1.

I give the two promised solutions.

If you have forget the problem, please reread

http://www.escribe.com/science/theory/m3079.html

The long term goal of this thread is G*, I recall.

Apology for those who would know those things.

The others can take their time (it's a long post)

for being sure everything is clear.

Any questions and/or remarks are welcome, 'course.

***

I rewrite the paradox (quoting myself):

*>I will say that a function f is computable if there is
*

*>a well defined formal language FL in which I can explained
*

*>non ambiguously how to compute f on arbitrary input (number).
*

I recall the functions are supposed to be functions whith

inputs in N and outputs in N. The functions are supposed to be

defined on *any* natural numbers.

*>I must be able to recognise if an expression in my language
*

*>is a grammaticaly correct definition of a function, that is
*

*>syntax error must be recoverable.
*

*>All expression in the language must be of finite length, and
*

*>the alphabet (the set of symbols) of the language is asked to
*

*>be finite.
*

*>Now all finite strings, a fortiori the grammatically correct
*

*>one, form a countable set. Just use the lexicographic order
*

*>defined above.
*

*>
*

*>So the set of function computable with FL is countable.
*

*>A synonym of countable is *enumerable*, and is used by
*

*>computer scientist, so I will also use it.
*

*>
*

*>So I can enumerate the functions computable with FL, that is
*

*>I can put them in sequence like f_0, f_1, f_2, f_3, ...
*

*>going through all functions computable in or with FL.
*

Sure.

*>Let us consider the function g defined again by
*

*>
*

*> g(n) = f_n(n) + 1
*

*>
*

*>Now, g is not only well defined, but is even computable.
*

Because each f_i are. It follows from our hypothesis. Of course

adding one is a computable operation.

*>To compute it on n, just search in the enumeration f_i the nth
*

*>function, apply it to n (this gives an answer because the f_i
*

*>are computable) and add 1.
*

So g is indeed computable.

*>So, there is a number k such that g = f_k, but then, again
*

*>
*

*> g(k) = f_k(k) = f_k(k) + 1
*

*>
*

*>But f_k(k) is a well defined number (f_k is computable), and
*

*>no numbers can be equal to "itself + 1". Contradiction.
*

*>Could the set of computable functions in FL be uncountable, after
*

*>all, or is g not expressible in FL, or what?
*

The expression "computable functions in FL" is an abbreviation

for the "computable functions *definissable* by an expression (a

string, a list, a number) in FL".

So, obviously, through the lexical ordering, the set of functions

computable in FL is countable, (enumerable, bijective with N).

By the same token the function g is obviously computable.

Yet, we have not prove that this set is uncountable.

So what?

For g being computable, it was important that the f_i could

be enumerated (unlike the f_i in Cantor proof which rely in

arbitrary order in Plato heaven).

THE FIRST WAY TO AVOID THE PARADOX

1 The first way to avoid the paradox consist in

precising our definition of LF: a formal language

defining computable function from N to N, and defining

*only* computable function.

That is we suppose all expressions in LF computes only

functions defined on all their arguments, the programs or

the machines computing them stop for any arguments. LF

defines only so called *total* computable functions.

In that case, (unless you believe 1 = 0), you are forced

to believe that the reasoning above shows only that the

function g, although total computable, is not LF expressible.

You cannot defined it in LF. LF has failed to capture the set

of *all* total computable functions. There is no k such that

the diagonal function g = f_k, f_k enumerating the LF-computable

functions. This gives:

THEOREM 1 there is no universal language capable of defining

all and only all total computable functions.

In term of the machine computing the functions described in

a language:

THEOREM 1 there is no universal machine computing all and only

all total computable functions.

In term of the enumeration of the f_i, the THEOREM 1, looks

like CANTOR theorem:

THEOREM 1 the set of machines (programs, expressions),

computing (programming, defining), total computable function

is not algorithmically countable. The logician say: not

recursively enumerable.

You cannot generate all and only all names of the total computable

functions.

Algebraist like to say a set is *closed* for an operation defined

in that set when the operation never leads ouside the set.

So an algebraic version of THEOREM 1 is

THEOREM 1 The set of (expression computing) all and only all

total computable function is not closed for the diagonalisation

operation.

CONSEQUENCES If you have a language L computing only total

computable functions, then you can build a new total computable

function outside the class defined by L.

This gives a tool for the refutation of all naive Pythagorian

School, believing that they can capture formally the set

of all and only all total computable functions.

Exemple: Suppose a naive Pythagorician believe that all

computable functions can be put into the form of the class of

functions defined by a positive polynomial: like "5x^3 + 2x^2 + 3".

The set of those polynomes is obviously recursively enumerable.

Let p_i be an enumeration of the polynomes. So the function

g such that g(n) = p_n(n) + 1 gives a non positive polynomial

computable function. Refuting the naive Pythagorician.

You can add g to the list of polynoms, of course, and you get

a new class of total computable functions, so that you can

diagonalise it again, and again, and again ..., and then

again again, ... iterating in the transfinite, for better

sub-approximations of the set of the everywhere defined machines.

THE SECOND WAY TO AVOID THE PARADOX

The THEOREM 1 says that you cannot find a universal language

capable of defining all and only all total computable functions.

A question remains: would it be possible that there exists a

universal language capable of defining all total computable

functions? (dropping the "and *only* all").

Well, there is a thesis for that effect. Indeed all attempt

of defining all computable functions leads to the same

class of computable functions (from Babbage, Post, Church, Turing,

... to Java, C++, ... to Deutsch Universal Quantum Machines).

So a version of Church thesis is that FORTRAN (let us say) is

a language defining all total computable functions (but then

by theorem 1, computing not only those total functions).

CHURCH THESIS There exists a universal language.

(and FORTRAN is the one).

In term of machine : There exits a universal machine

(and the interpreter LISP is the one).

As a consequence of theorem 1, we can expect that if such

a universal language exists (i.e. Church thesis) then it will

defined all total functions, but certainly not all *and only*

all total functions.

That is, it will defined all total functions *and other sort

of beast* as a necessary gift.

So the second way to avoid the paradox consist in dropping the

"and only" in "language capable of defining all and only all

total computable functions". We precise our formal system in

a more liberal way by dropping the totality constraint.

What does happen with the diagonalisation, with such a universal

language? (Let us take FORTRAN for fixing the idea).

Well, you certainly can generate mechanically (recursively enumerate)

the list of all programs FORTRAN, still by lexicographical order.

So let F_i be an enumeration of the fortran programs.

The diagonal function g, such that g(n) = F_n(n) + 1, is certainly

programmable, just because you can write a generator of the F_i,

and an applicator of the F_i on an input i, and you have an adder

for the "+ 1".

So there is certainly a F_k such that g = F_k.

So what? What will happen when you run g_k(k)?

One thing is sure, if the machine stop on g_k(k), then

g_k(k) = g_k(k) + 1. So the machine will simply not stop!

In the computer scientist jargon we say that the universal

machine crash. The machine get on his/her/it way, remain

silent, and simply does not stop.

This proves g is undefined on k, its own number in the

enumeration of the programs. g is not a total computable

functions (being not defined everywhere

So we get

THEOREM 2 All languages (machines) defining (computing)

all total computable functions, defined automatically

a vaster set containing *partial* computable functions.

In particular all diagonal functions g are undefined

on their own code.

We get immediately (with Church Thesis), the insolubility

result:

THEOREM 3 there is no program (machines) capable of deciding if

the code of F_i correspond to a total function or not.

Proof: Because, if that was the case, you could mechanically

extract a recursive enumeration of the total computable

function by deleting the code of the non total functions in

the enumeration of the F_i. (contradicting theorem 1).

THEOREM 4 (Incompleteness):

Any theory in which you can represent the (total or partial)

computable functions cannot be complete.

That is for any such theory you can find true proposition which

cannot be proved in the theory.

Proof:

If the theory was complete, that is capable of proving all

true propositions expressible in its language (supposed being

enough rich for representing the partial recursive functions),

then you could use the theory again for extracting a recursive

enumeration

of the total computable functions (by deleting again the code of

the non total functions in the enumeration of the F_i (and this

you do by testing the proposition "F_i is not-total" in your

complete theory))).

(Peano Arithmetic or Zermelo Fraenkel Set Theory are exemples of such

theories, i.e. rich enough for representing the F_i. But showing

this, although easy, is tedious, a little like programming in assembly

language). Any axiomatisable extension of those theories succumb

the same godelian incompleteness fate.

Bruno

Received on Thu Oct 18 2001 - 10:27:38 PDT

Date: Thu Oct 18 10:27:38 2001

To all victims of certainties.

Hi all,

Thanks for those who makes out-of-line comments of

Diagonalisation 1.

I give the two promised solutions.

If you have forget the problem, please reread

http://www.escribe.com/science/theory/m3079.html

The long term goal of this thread is G*, I recall.

Apology for those who would know those things.

The others can take their time (it's a long post)

for being sure everything is clear.

Any questions and/or remarks are welcome, 'course.

***

I rewrite the paradox (quoting myself):

I recall the functions are supposed to be functions whith

inputs in N and outputs in N. The functions are supposed to be

defined on *any* natural numbers.

Sure.

Because each f_i are. It follows from our hypothesis. Of course

adding one is a computable operation.

So g is indeed computable.

The expression "computable functions in FL" is an abbreviation

for the "computable functions *definissable* by an expression (a

string, a list, a number) in FL".

So, obviously, through the lexical ordering, the set of functions

computable in FL is countable, (enumerable, bijective with N).

By the same token the function g is obviously computable.

Yet, we have not prove that this set is uncountable.

So what?

For g being computable, it was important that the f_i could

be enumerated (unlike the f_i in Cantor proof which rely in

arbitrary order in Plato heaven).

THE FIRST WAY TO AVOID THE PARADOX

1 The first way to avoid the paradox consist in

precising our definition of LF: a formal language

defining computable function from N to N, and defining

*only* computable function.

That is we suppose all expressions in LF computes only

functions defined on all their arguments, the programs or

the machines computing them stop for any arguments. LF

defines only so called *total* computable functions.

In that case, (unless you believe 1 = 0), you are forced

to believe that the reasoning above shows only that the

function g, although total computable, is not LF expressible.

You cannot defined it in LF. LF has failed to capture the set

of *all* total computable functions. There is no k such that

the diagonal function g = f_k, f_k enumerating the LF-computable

functions. This gives:

THEOREM 1 there is no universal language capable of defining

all and only all total computable functions.

In term of the machine computing the functions described in

a language:

THEOREM 1 there is no universal machine computing all and only

all total computable functions.

In term of the enumeration of the f_i, the THEOREM 1, looks

like CANTOR theorem:

THEOREM 1 the set of machines (programs, expressions),

computing (programming, defining), total computable function

is not algorithmically countable. The logician say: not

recursively enumerable.

You cannot generate all and only all names of the total computable

functions.

Algebraist like to say a set is *closed* for an operation defined

in that set when the operation never leads ouside the set.

So an algebraic version of THEOREM 1 is

THEOREM 1 The set of (expression computing) all and only all

total computable function is not closed for the diagonalisation

operation.

CONSEQUENCES If you have a language L computing only total

computable functions, then you can build a new total computable

function outside the class defined by L.

This gives a tool for the refutation of all naive Pythagorian

School, believing that they can capture formally the set

of all and only all total computable functions.

Exemple: Suppose a naive Pythagorician believe that all

computable functions can be put into the form of the class of

functions defined by a positive polynomial: like "5x^3 + 2x^2 + 3".

The set of those polynomes is obviously recursively enumerable.

Let p_i be an enumeration of the polynomes. So the function

g such that g(n) = p_n(n) + 1 gives a non positive polynomial

computable function. Refuting the naive Pythagorician.

You can add g to the list of polynoms, of course, and you get

a new class of total computable functions, so that you can

diagonalise it again, and again, and again ..., and then

again again, ... iterating in the transfinite, for better

sub-approximations of the set of the everywhere defined machines.

THE SECOND WAY TO AVOID THE PARADOX

The THEOREM 1 says that you cannot find a universal language

capable of defining all and only all total computable functions.

A question remains: would it be possible that there exists a

universal language capable of defining all total computable

functions? (dropping the "and *only* all").

Well, there is a thesis for that effect. Indeed all attempt

of defining all computable functions leads to the same

class of computable functions (from Babbage, Post, Church, Turing,

... to Java, C++, ... to Deutsch Universal Quantum Machines).

So a version of Church thesis is that FORTRAN (let us say) is

a language defining all total computable functions (but then

by theorem 1, computing not only those total functions).

CHURCH THESIS There exists a universal language.

(and FORTRAN is the one).

In term of machine : There exits a universal machine

(and the interpreter LISP is the one).

As a consequence of theorem 1, we can expect that if such

a universal language exists (i.e. Church thesis) then it will

defined all total functions, but certainly not all *and only*

all total functions.

That is, it will defined all total functions *and other sort

of beast* as a necessary gift.

So the second way to avoid the paradox consist in dropping the

"and only" in "language capable of defining all and only all

total computable functions". We precise our formal system in

a more liberal way by dropping the totality constraint.

What does happen with the diagonalisation, with such a universal

language? (Let us take FORTRAN for fixing the idea).

Well, you certainly can generate mechanically (recursively enumerate)

the list of all programs FORTRAN, still by lexicographical order.

So let F_i be an enumeration of the fortran programs.

The diagonal function g, such that g(n) = F_n(n) + 1, is certainly

programmable, just because you can write a generator of the F_i,

and an applicator of the F_i on an input i, and you have an adder

for the "+ 1".

So there is certainly a F_k such that g = F_k.

So what? What will happen when you run g_k(k)?

One thing is sure, if the machine stop on g_k(k), then

g_k(k) = g_k(k) + 1. So the machine will simply not stop!

In the computer scientist jargon we say that the universal

machine crash. The machine get on his/her/it way, remain

silent, and simply does not stop.

This proves g is undefined on k, its own number in the

enumeration of the programs. g is not a total computable

functions (being not defined everywhere

So we get

THEOREM 2 All languages (machines) defining (computing)

all total computable functions, defined automatically

a vaster set containing *partial* computable functions.

In particular all diagonal functions g are undefined

on their own code.

We get immediately (with Church Thesis), the insolubility

result:

THEOREM 3 there is no program (machines) capable of deciding if

the code of F_i correspond to a total function or not.

Proof: Because, if that was the case, you could mechanically

extract a recursive enumeration of the total computable

function by deleting the code of the non total functions in

the enumeration of the F_i. (contradicting theorem 1).

THEOREM 4 (Incompleteness):

Any theory in which you can represent the (total or partial)

computable functions cannot be complete.

That is for any such theory you can find true proposition which

cannot be proved in the theory.

Proof:

If the theory was complete, that is capable of proving all

true propositions expressible in its language (supposed being

enough rich for representing the partial recursive functions),

then you could use the theory again for extracting a recursive

enumeration

of the total computable functions (by deleting again the code of

the non total functions in the enumeration of the F_i (and this

you do by testing the proposition "F_i is not-total" in your

complete theory))).

(Peano Arithmetic or Zermelo Fraenkel Set Theory are exemples of such

theories, i.e. rich enough for representing the F_i. But showing

this, although easy, is tedious, a little like programming in assembly

language). Any axiomatisable extension of those theories succumb

the same godelian incompleteness fate.

Bruno

Received on Thu Oct 18 2001 - 10:27:38 PDT

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*