On 14/01/2013 4:46 AM, Kassen wrote:
> On Sun, Jan 13, 2013 at 05:07:44PM +0000, Click Nilson wrote:
>> >(though space for output and intermediate storage may be an issue).
> That's what I was hinting at.
>
> To be able to compute any arbitrary computable thing you will need
> that space and I really don't think there is a way around that.
>
> That's established in theory and entirely irrelevant in practice,
> though it was somewhat amusing to apply the dusty old theory to the
> field of human computation.
I think it's possible (at least in an informal setting) to require
universal computation without requiring infinite space:
"""
In colloquial usage, the terms "Turing complete" or "Turing equivalent"
are used to mean that any real-world general-purpose computer or
computer language can approximately simulate any other real-world
general-purpose computer or computer language, within the bounds of
finite memory – they are linear bounded automaton complete. A universal
computer is defined as a device with a Turing complete instruction set,
infinite memory, and an infinite lifespan; all general purpose
programming languages and modern machine instruction sets are Turing
complete, apart from having finite memory.
"""
--
http://en.wikipedia.org/wiki/Turing_completeness
R.
Received on Sun Jan 13 2013 - 18:04:43 GMT