Church's Heresy and the Unsolveability of chess

Thread View: sci.logic

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Mark Tue, 06 Oct 1992 03:29

#450

Author: Mark
Date: Tue, 06 Oct 1992 03:29

13 lines
1064 bytes

   Call this Church's Heresy:  the set of all computable functions is a finite
set, and a proper subset of the recursive functions.

Application:
   The game solving algorithm is not (yet) computable with the input being
the game of chess.  Thus, by Church's Heresy, chess is not (yet) computable.

   The strong version of Church's Heresy: the set of all functions that have
been, are being, ever will be, or ever could be computed is a finite subset
of the recursive functions bounded above in size by 2-to-the-256.

Corollary:  Every computable function can be represented uniquely by 32 bytes.
Theorem:    This 32-byte coding is not computable, but is finite and recursive.

Re: Church's Heresy and the Unsolveability of chess

#457

Author: Torben AEgidius Mogensen
Date: Tue, 06 Oct 1992 11:28

13 lines
1055 bytes

markh@csd4.csd.uwm.edu (Mark) writes:

>   The strong version of Church's Heresy: the set of all functions that have
>been, are being, ever will be, or ever could be computed is a finite subset
>of the recursive functions bounded above in size by 2-to-the-256.

>Corollary: Every computable function can be represented uniquely by 32 bytes.
>Theorem:   This 32-byte coding is not computable, but is finite and recursive.

No. It is only the size of the functions that can be represented in 32
bytes. The functions themselves needs 2^256 bytes.

	Torben Mogensen (torbenm@diku.dk)

Re: Church's Heresy and the Unsolveability of chess

#461

Author: Mark
Date: Tue, 06 Oct 1992 20:23

18 lines
1375 bytes

I expound on The Church's Heresy:
>   The strong version of Church's Heresy: the set of all functions that have
>been, are being, ever will be, or ever could be computed is a finite subset
>of the recursive functions bounded above in size by 2-to-the-256.

>Corollary: Every computable function can be represented uniquely by 32 bytes.
>Theorem:   This 32-byte coding is not computable, but is finite and recursive.

In article <1992Oct6.112819.16016@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>No. It is only the size of the functions that can be represented in 32
>bytes. The functions themselves needs 2^256 bytes.

There are 2^256 32 byte integers.  Therefore there is a one-to-one
correspondence between 32 byte integers and computeable functions (which
there are less than 2^256 of).

Furthermore, this mapping is finite, therefore it is a recursive function.
It's just not computeable.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads