5 ms·

Logically infinite if not practically infinite. Python specifies a language which has access to logically infinite amounts of memory: it's an implementation det

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.

Pharylon 9y ago
But by this definition, C isn't Turing Complete either. https://cs.stackexchange.com/questions/60965/is-c-actually-turing-complete https://cs.stackexchange.com/questions/60965/is-c-actually-t...
- deleted 9y ago
  [deleted]
- bluGill 9y 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)
  - Smaug123 9y 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?
    - bluGill 9y 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.
- Smaug123 9y 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.
  - empath75 9y ago
    If we're doing that why not just imagine a PowerPoint presentation that's not bounded?
    - Smaug123 9y 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.

Pharylon 9y ago

But by this definition, C isn't Turing Complete either. https://cs.stackexchange.com/questions/60965/is-c-actually-turing-complete https://cs.stackexchange.com/questions/60965/is-c-actually-t...

deleted 9y ago
[deleted]
bluGill 9y 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)
- Smaug123 9y 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?
  - bluGill 9y 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.
Smaug123 9y 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.
- empath75 9y ago
  If we're doing that why not just imagine a PowerPoint presentation that's not bounded?
  - Smaug123 9y 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.