Article View: sci.logic
Article #457Re: Church's Heresy and the Unsolveability of chess
From: Torben AEgidius Mogensen
Date: Tue, 06 Oct 1992 11:28
Date: Tue, 06 Oct 1992 11:28
13 lines
1055 bytes
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)
Technical Details
Message-ID:
<1992Oct6.112819.16016@odin.diku.dk>Path:
arc1-ca.pugleaf.net!sparky!uunet!sun-barr!olivea!spool.mu.edu!agate!doc.ic.ac.uk!uknet!mcsun!sunic!dkuug!diku!torbenmReferences:
<1ar16rINNp9e@uwm.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!sparky!uunet!sun-barr!olivea!spool.mu.edu!agate!doc.ic.ac.uk!uknet!mcsun!sunic!dkuug!diku!torbenm From: torbenm@diku.dk (Torben AEgidius Mogensen) Newsgroups: sci.logic Subject: Re: Church's Heresy and the Unsolveability of chess Message-ID: <1992Oct6.112819.16016@odin.diku.dk> Date: 6 Oct 92 11:28:19 GMT References: <1ar16rINNp9e@uwm.edu> Sender: torbenm@freke.diku.dk Organization: Department of Computer Science, U of Copenhagen Lines: 13