11–20 of 23 posts
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
(This is also why C is not Turing complete.)
I'm asking because since the true definition of a Turing machine requires infinite memory, in theory nothing can be a Turing machine in the observable universe, so this definition doesn't help describe anything that's used in practice.
On the other hand, there's an obvious difference in power of a language like C, versus non Turing-complete languages like regexp. So it's useful to talk about this concept, but we could never formally call any of those Turing complete (C pointers are limited to so many bits, for example).
The discussion about this detail comes up every time, so is there some proper formal term for this?
Something related to how much code is required to use the finite pool of memory you have in any way you want, or so (where a non turing complete language may require enumerating all possibilites and thus too large code size)
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
(This is also why C is not Turing complete.)
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using ` `) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a] [a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle…
I disagree that this proves the Turing completeness of CSS. Part of the definition of Turing machines is access to unbounded memory. In Python, for example, we meet this requirement by saying that any underlying request to new memory will succeed, or we can imagine an implementation of Python without a stack limit and lambda-encode everything. Ultimately, Python as an abstract language has no memory limitations, that…
Enumerating and memoizing all possible states will still be impractical, even for small machines.
Earlier quoted context omitted.
That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using ` `) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a] [a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle…
Actually, I thought you don’t even need unbounded memory because it’s proven that the register machine [0] with limited memory is still Turing complete. [0] https://en.wikipedia.org/wiki/Register_machine
Earlier quoted context omitted.
That's getting pretty technical. It can execute Rule 110, therefore it's Turing Complete because infinite memory is impossible. Stating how many cells you need beforehand (using ` `) isn't much different from stating that my laptop only has 16 gigabytes of RAM. Sure, you need to encode that beforehand, but so do the RAM modules.[a] [a]: This is usually accomplished with a tiny SOIC-8 IC on the module (see the middle…
Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.
This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and like anything we do on modern computers, can be reduced to assembly where again memory has to be 'described'. Python may hide it for us but it's there.
Earlier quoted context omitted.
Actually, I thought you don’t even need unbounded memory because it’s proven that the register machine [0] with limited memory is still Turing complete. [0] https://en.wikipedia.org/wiki/Register_machine
Abstract register machines are normally considered to have infinite memory - because even though the number of registers can be bounded, their size is often not. Unlike the fixed-width registers of a real CPU, abstract registers are typically capable of storing any positive integer.
Earlier quoted context omitted.
Without speaking for the OP, it seems like the case being made is not that the result is executed on a real, finite machine approximation (as all programs are) but that there exists an abstract Python machine wherein the memory does not need to be so described. This does not exist for CSS.
> that there exists an abstract Python machine wherein the memory does not need to be so described This is getting a little esoteric. Python interpreters are created in other languages like C where memory does need to be described. How can this 'abstract Python machine' even be implemented? Python or any higher level interpreted language will always have the same limitations of the language it's implemented in and li…