Hacker News new | ask | show | jobs
by Smaug123 3282 days ago
Logically infinite if not practically infinite. Python specifies a language which has access to logically infinite amounts of memory: it's an implementation detail that there's an upper bound on the size of tape it can simulate on a computer. PPTXTM is by design unable to simulate unbounded tapes.
1 comments
Pharylon 3282 days ago
But by this definition, C isn't Turing Complete either.

https://cs.stackexchange.com/questions/60965/is-c-actually-t...

link
bluGill 3282 days ago
When talking about Turing completeness I use an alternate definition of infinity that I call practically infinite: for a given a program that halts on an arbitrary Turing machine it also halts on this specific on. I call this practical Turing completeness (though I suspect the literature has already considered this idea and has a different term)
link
Smaug123 3282 days ago
Could you be more precise, please? I'm afraid I don't understand the definition you've given. Can you make your quantifiers explicit?
link
bluGill 3282 days ago
I mean that the technical limits are a not an issue for the program you want to run. Hello World will run on an AppleII computer, but it doesn't have enough memory to run Libre Office (Assume an unlimited budget to create/port the compiler, POSIX layer, X server ...)

If the conversation is concerned with running Hello world it doesn't matter that an AppleII can't do everything, for our purposes it can do anything. If we expand the conversation a little but though we realize this machine is unable to run many things we find useful today.

link
Smaug123 3282 days ago
I'm happy with that. It's an explicit design decision of C that there is a bound on the number of pointers. If I want to consider a Turing-complete variant, all I need to do is let pointers be of arbitrary size somehow, or let it have an "integer" type which really does hold any size of integer.
link
empath75 3282 days ago
If we're doing that why not just imagine a PowerPoint presentation that's not bounded?
link
Smaug123 3282 days ago
Sure. PPTXTM+unbounded is to PPTXTM as C-with-integers is to C, and as Python is to Python-whose-specification-limits-it-to-boundedly-many-objects.
link