Hacker News Reader

Comment by colejohnson66 | Hacker News Reader

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 `<input type="checkbox"/>`) 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 of the top of [0])

[0]: https://upload.wikimedia.org/wikipedia/commons/d/db/Swissbit...

View on HN

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.

I’m aware and that’s how they are usually introduced. However, there’s also the model of such that have a further restricted set of instructions and only have limited memory.

Could you please give a reference for such a model, and the proof that it's Turing complete? I don't see it described on the Wikipedia page, which explicitly states that registers are unbounded.

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.

Why not? I can imagine a modified abstract css machine which applies the styles to an infinitely long html document. That's much more contrived than the python case, but if we are going to be making arbitrary changes from finite machines, im not sure under what basis we would draw the line.

The html document is potentially infinite, but its finite length is not encoded in the program (css).

One idea is, to have the same program, and if it terminates, it will terminate if you pick a large enough machine. You don't need to "rewrite" the program to use a larger machine.

So in this case the html document is the tape. Potentially infinite, but not in reality. The css program may handle it as infinite.

>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 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.

>How can this 'abstract Python machine' even be implemented?

It wouldn't be - the machine is abstract. It exists only in terms of a mathematical model, that describes how Python code behaves in a defined mathematical way (its semantics). The real implementations of Python should have the same behaviour as the abstract machine, but the property of Turing-completeness really only exists for the abstract version - the real versions, being bounded in memory, are limited to certain sizes of programs.

Reply on news.ycombinator.com