Hacker News Reader

Comment by simcop2387 | Hacker News Reader

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.

View on HN

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.

What IO capabilities does the lambda calculus have?

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.

Reply on news.ycombinator.com