4 ms·

Too many things are Turing Complete. I would like to propose more research into things which are "Tetris Complete". https://everything2.com/title/Tetris+comple

Too many things are Turing Complete. I would like to propose more research into things which are "Tetris Complete". https://everything2.com/title/Tetris+complete https://everything2.com/title/Tetris+complete Tetris Completion extends Turing Completion by adding the minimum requirements for a functional implementation of Tetris. From the link above: * a display with at least 20 rows and 10 columns, and enough read/write random access memory to store the current contents of the display, * a way of repainting one row or column of the display without affecting the others, * a timer with a resolution of at least 100 milliseconds * a small set of keys whose state can be read without blocking execution, which for Tetris are left, right, clockwise, and anticlockwise * a linear bounded automaton programmed for the particular puzzle game

stellaathena 5y ago
Tetris can be programmed on a computer, ergo anything that is Turing Complete can simulate Tetris. What am I missing?
- simcop2387 5y ago
  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.
  - stellaathena 5y ago
    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.
    - 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 ago
      What IO capabilities does the lambda calculus have?
    - simcop2387 5y ago
      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.
- charcircuit 5y ago
  Tetris can be programmed on something that isn't Turing Complete.
grishka 5y ago
Also there are things that are Doom Complete and Bad Apple Complete.
- jwdunne 5y ago
  Yeah, I was about to mention Doom. There’s a whole subreddit dedicated to running Doom on the weird and wonderful. Even had an eInk device running Doom, which looked painful but cool.
otabdeveloper4 5y ago
Anything that can recurse or fall into an infinite loop is Turing complete. (It's not a very interesting property.) Much more interesting is what we can compute without Turing completeness. (Shameless plug: https://tkatchev.bitbucket.io/tab/index.html https://tkatchev.bitbucket.io/tab/index.html)
- charcircuit 5y ago
  >Anything that can recurse or fall into an infinite loop is Turing complete. My computer can fall into an infinite loop even though it doesn't have infinite storage (to emulate an infinite tape of a Turing machine).
  - burrows 5y ago
    No it can’t because there isn’t infinite energy.
    - charcircuit 5y ago
      I never said that my computer would run forever. I simply stated that it would fall into an infinite loop. You could argue that cosmic rays could cause a bit flip to get the computer out of an infinite loop, but that it is out of scope.
      - burrows 5y ago
        Does the program halt when the power cuts out? I think our disagreement is specious because it’s trying to import terms like “infinite loop”, “halt”, “program” from a formal theory into the material world. I think I can only ask, how do you define infinite loop and forever?
        charcircuit 5y ago
        >Does the program halt when the power cuts out? Yes. A computer can be in an infinite loop, lose power, and then stop functioning. >how do you define infinite loop and forever Infinite Loop: A system is in an infinite loop when that system keeps returning to the same state making it unable to progress (depending on the context the definition might change to where making progress is okay and it in only returning to a partial match of an existing state (think of an echo server for example)) Forever: A time period that ranges from t=now to t=infinity.

stellaathena 5y ago

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

simcop2387 5y ago
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.
- stellaathena 5y ago
  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.
  - 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 ago
    What IO capabilities does the lambda calculus have?
  - simcop2387 5y ago
    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.
charcircuit 5y ago
Tetris can be programmed on something that isn't Turing Complete.

grishka 5y ago

Also there are things that are Doom Complete and Bad Apple Complete.

jwdunne 5y ago
Yeah, I was about to mention Doom. There’s a whole subreddit dedicated to running Doom on the weird and wonderful. Even had an eInk device running Doom, which looked painful but cool.

otabdeveloper4 5y ago

Anything that can recurse or fall into an infinite loop is Turing complete. (It's not a very interesting property.) Much more interesting is what we can compute without Turing completeness. (Shameless plug: https://tkatchev.bitbucket.io/tab/index.html https://tkatchev.bitbucket.io/tab/index.html)

charcircuit 5y ago
>Anything that can recurse or fall into an infinite loop is Turing complete. My computer can fall into an infinite loop even though it doesn't have infinite storage (to emulate an infinite tape of a Turing machine).
- burrows 5y ago
  No it can’t because there isn’t infinite energy.
  - charcircuit 5y ago
    I never said that my computer would run forever. I simply stated that it would fall into an infinite loop. You could argue that cosmic rays could cause a bit flip to get the computer out of an infinite loop, but that it is out of scope.
    - burrows 5y ago
      Does the program halt when the power cuts out? I think our disagreement is specious because it’s trying to import terms like “infinite loop”, “halt”, “program” from a formal theory into the material world. I think I can only ask, how do you define infinite loop and forever?
      - charcircuit 5y ago
        >Does the program halt when the power cuts out? Yes. A computer can be in an infinite loop, lose power, and then stop functioning. >how do you define infinite loop and forever Infinite Loop: A system is in an infinite loop when that system keeps returning to the same state making it unable to progress (depending on the context the definition might change to where making progress is okay and it in only returning to a partial match of an existing state (think of an echo server for example)) Forever: A time period that ranges from t=now to t=infinity.