Hacker News Reader

Comment by stellaathena | Hacker News Reader

Tetris can be programmed on a computer, ergo anything that is Turing Complete can simulate Tetris. What am I missing?

Computationally this is correct, however the tetris complete definition also sets requirements to interface with the outside world, in particular the timing and I outs aren't covered by turing completeness. a turing cokplete system could require villions of years to simulate a game of tetris and still be turing complete.

I/O is covered by Turing completeness. Whether timing is depends significantly on how exactly you want to formalize things, but certainly any TC system has the capacity to keep track of time if the pieces are manipulated at a constant rate.

> I/O is covered by Turing completeness.

Not really. A plain turing machine only has one input and one output over the lifetime of the execution.

> certainly any TC system has the capacity to keep track of time if the pieces are manipulated at a constant rate.

Only if the turing-equivalent machine is iterating at a specific rate and can pause. Lots of these systems run through the entire machine in a single shot and can't manage timing.

It's not so much keeping track of time, but that that time matches the real world outside the machine. The whole Tetris Complete formalization is about how a given machine (which as a previous comment points out, doesn't need to be turing complete) relates to the non-theoretical non-computational world. Turing completeness requires or even suggests any of those things, it's an orthogonal concept.

What IO capabilities does the lambda calculus have?

Tetris can be programmed on something that isn't Turing Complete.

Reply on news.ycombinator.com