6 ms·
Tetris can be programmed on a computer, ergo anything that is Turing Complete can simulate Tetris. What am I missing?
by stellaathena 5y ago
Tetris can be programmed on a computer, ergo anything that is Turing Complete can simulate Tetris. What am I missing?
- charcircuit 5y agoTetris can be programmed on something that isn't Turing Complete.
- simcop2387 5y agoComputationally 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.
- stellaathena 5y agoI/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.
- simcop2387 5y agoIt'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.
- Dylan16807 5y ago> 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.
- carnitine 5y agoWhat IO capabilities does the lambda calculus have?