Hacker News Reader

Comment by CJefferson | Hacker News Reader

I'd like a more complete description of this.

My first thought is "no it's not", because you are encoding a fixed-sized grid in the HTML, which is then the total extent of the program. While no real machine has an "infinite tape", I think requiring the tape be embedded in the program itself is strengthing things a little far.

View on HN

Why is it stretching things a little far? Non-infinite tape is, as you noted, a limit on everything we consider turing complete: this is just running at a much higher level of abstraction than your computer. You could (if you were so inclined) create a physical machine with a grid of memory that behaved according to rules defined by CSS selectors. Just because this doesn't do direct memory access and behave like the computer or a traditional TM doesn't make it not a TM. (Or, at least, any less of a TM than the computer you're using.)

The real question is if this can deal with arbitrary amounts of finite memory. That is, could I express an instance of a program that requires a trillion "units" of memory w/o constructing a new "machine" that explicitly laid it out?

Is my MacBook Pro any more Turing complete? All of the memory came with it. There's no way to expand the memory as it's running.

But the HTML is not the program; it's the machine that runs the program. In that view, the tape being finite is just like the tape (RAM, disk, mercury delay lines) of a physical machine being finite.

Reply on news.ycombinator.com