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

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

Date: Mon, 5 Jun 2006 14:27:51 +0200

More comments on George Levy + *THE PUZZLE*.

Le 30-mai-06, à 20:42, George Levy a écrit :

*>
*

*> To speak only for myself, I think I have a sufficient understanding of
*

*> the thread. Essentially you have shown that one cannot form a set of
*

*> all
*

*> numbers/functions because given any set of numbers/functions it is
*

*> always possible, using diagonalization, to generate new
*

*> numbers/functions: the Plenitude is too large to be a set.
*

The first person plenitude will be too large or too complex to be a

mechanically generable set.

Just to give the exact wording of the conclusion. The explanation will

follow. I am glad you describe the tranfinite extensions of the set of

(growing or not) computable functions as a plenitude, and it models

indeed well the notion of first person plenitude on which we will

converge with Church thesis, and which describes a quasi solipsistic

transfinitely self-extending self, building from "controllable sets" to

bigger one.

But the sequel should show how Church thesis will force us to accept a

third person comp realm which will somehow transcend the limitation of

the first person, but then with *the* big price.

*> This leads to
*

*> a problem with the assumption of the existence of a Universal
*

*> Dovetailer
*

*> whose purpose is to generate all functions. I hope this summary is
*

*> accurate.
*

Completely. Let me give you *the puzzle*. What is wrong with the

following "refutation" of Church thesis:

Let me just recall what is a computable function from N to N. It is

function from N to N which is such that it is exist a finite way to

explain how to compute it in a finite number of steps on any natural

numbers. More precisely: f is computable if there is a language L such

that f admits a finite code/program/description/number explaining how

to compute f(n), in a finite time on any number natural n.

I will say that that a language L is universal, if all computable

functions from N to N admit a code in L.

A weak form of Church thesis can be put in this way: there exists a

universal language.

I will say a digital (or finitely describable) machine M is universal

if M can "understand" a universal language L, in the sense of being

able to compute any computable functions described in L (and thus all

given that L is universal) . In term of digital machine, Church thesis

becomes: there exists a universal digital machine.

Now what is wrong with the following argument: if there is an universal

language or machine, the computable functions can be described by

finite description in that language, or program for that machine.

Such a set is obviously enumerable. There is a bijection between N and

the set of those descriptions:

1 f1

2 f2

3 f3

4 f4

etc.

So the following function g is well-defined by:

g(n) = fn(n) + 1

Then, to compute it on the number n (439 say), just generate the

description/program of f1 f2 f3 ... until fn, that is f439, apply it

on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is

here: f439(439)+1.

But then g cannot be described in the language L! Why? Suppose g is

described by a code in the language L: then g belongs somewhere in the

list f1, f2, f3, f4, f5, .... Thus there would exist a number k such

that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus

fK(k) = fk(k)+1 (*)

And fk(k) is a well defined number given that the fi are all computable

functions from N to N. So I can substract fk(k) on both sides of (*)

just above, and I get 0 = 1 (contradiction). So there is no universal

language, we cannot generate all computable functions, still less,

then, to dovetail on them.

Where is the error? How could Church still assert that its

"lambda-conversion calculus" (an ancestor of Lisp) is universal? What

about Fortran, Lisp, Python or other Rational Unitary Matrices?

I (re)assure you (?), I will keep Church thesis, without which there is

no just no UD. What does the above reasoning really prove then? What

price will be asked upon us for keeping consistently our belief in

universal language and universal machine?

It is not important to find the answer, but it will be capital to

understand it, and for that, it is capital to get the question, to see

the problem. I think that you, George, have seen the problem, and I am

just making higher the probability that others see as clearly as

possible the problem too. Hal and Jesse made big hints toward the

solution but I am not sure they have put the fingers on the very very

pricy consequence (?).

Bruno

PS Rereading some recent mails I wrote, I am ashamed of my style (when

I complete a sentences!) and by my enduring mishandling of the

singular/plural (the "s" problem). Please accept my apologies, and

don't hesitate to correct me or to ask questions in front of

ambiguities. Thanks for the interest anyway.

http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~

You received this message because you are subscribed to the Google Groups "Everything List" group.

To post to this group, send email to everything-list.domain.name.hidden

To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list

-~----------~----~----~----~------~----~------~--~---

Received on Mon Jun 05 2006 - 08:29:06 PDT

Date: Mon, 5 Jun 2006 14:27:51 +0200

More comments on George Levy + *THE PUZZLE*.

Le 30-mai-06, à 20:42, George Levy a écrit :

The first person plenitude will be too large or too complex to be a

mechanically generable set.

Just to give the exact wording of the conclusion. The explanation will

follow. I am glad you describe the tranfinite extensions of the set of

(growing or not) computable functions as a plenitude, and it models

indeed well the notion of first person plenitude on which we will

converge with Church thesis, and which describes a quasi solipsistic

transfinitely self-extending self, building from "controllable sets" to

bigger one.

But the sequel should show how Church thesis will force us to accept a

third person comp realm which will somehow transcend the limitation of

the first person, but then with *the* big price.

Completely. Let me give you *the puzzle*. What is wrong with the

following "refutation" of Church thesis:

Let me just recall what is a computable function from N to N. It is

function from N to N which is such that it is exist a finite way to

explain how to compute it in a finite number of steps on any natural

numbers. More precisely: f is computable if there is a language L such

that f admits a finite code/program/description/number explaining how

to compute f(n), in a finite time on any number natural n.

I will say that that a language L is universal, if all computable

functions from N to N admit a code in L.

A weak form of Church thesis can be put in this way: there exists a

universal language.

I will say a digital (or finitely describable) machine M is universal

if M can "understand" a universal language L, in the sense of being

able to compute any computable functions described in L (and thus all

given that L is universal) . In term of digital machine, Church thesis

becomes: there exists a universal digital machine.

Now what is wrong with the following argument: if there is an universal

language or machine, the computable functions can be described by

finite description in that language, or program for that machine.

Such a set is obviously enumerable. There is a bijection between N and

the set of those descriptions:

1 f1

2 f2

3 f3

4 f4

etc.

So the following function g is well-defined by:

g(n) = fn(n) + 1

Then, to compute it on the number n (439 say), just generate the

description/program of f1 f2 f3 ... until fn, that is f439, apply it

on n to get fn(n), f439(439), and add 1 to get g(n) = fn(n)+1, that is

here: f439(439)+1.

But then g cannot be described in the language L! Why? Suppose g is

described by a code in the language L: then g belongs somewhere in the

list f1, f2, f3, f4, f5, .... Thus there would exist a number k such

that g = fk, and thus g(k) = fk(k); but g(k) = fk(k)+1. And thus

fK(k) = fk(k)+1 (*)

And fk(k) is a well defined number given that the fi are all computable

functions from N to N. So I can substract fk(k) on both sides of (*)

just above, and I get 0 = 1 (contradiction). So there is no universal

language, we cannot generate all computable functions, still less,

then, to dovetail on them.

Where is the error? How could Church still assert that its

"lambda-conversion calculus" (an ancestor of Lisp) is universal? What

about Fortran, Lisp, Python or other Rational Unitary Matrices?

I (re)assure you (?), I will keep Church thesis, without which there is

no just no UD. What does the above reasoning really prove then? What

price will be asked upon us for keeping consistently our belief in

universal language and universal machine?

It is not important to find the answer, but it will be capital to

understand it, and for that, it is capital to get the question, to see

the problem. I think that you, George, have seen the problem, and I am

just making higher the probability that others see as clearly as

possible the problem too. Hal and Jesse made big hints toward the

solution but I am not sure they have put the fingers on the very very

pricy consequence (?).

Bruno

PS Rereading some recent mails I wrote, I am ashamed of my style (when

I complete a sentences!) and by my enduring mishandling of the

singular/plural (the "s" problem). Please accept my apologies, and

don't hesitate to correct me or to ask questions in front of

ambiguities. Thanks for the interest anyway.

http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~

You received this message because you are subscribed to the Google Groups "Everything List" group.

To post to this group, send email to everything-list.domain.name.hidden

To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden

For more options, visit this group at http://groups.google.com/group/everything-list

-~----------~----~----~----~------~----~------~--~---

Received on Mon Jun 05 2006 - 08:29:06 PDT

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