Hacker News Reader

Comment by LeoPanthera | Hacker News Reader

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

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

View on HN

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)

>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).

No it can’t because there isn’t infinite energy.

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.

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?

>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.

> Yes. A computer can be in an infinite loop, lose power, and then stop functioning.

Ok. Are these claims accurate?

1. All physical systems must eventually halt.

2. In many cases physical systems correspond to formal computational systems.

> Infinite Loop: A system is in an infinite loop when that system keeps returning to the same state making it unable to progress

A system is called deterministic if all future states can be calculated from complete knowledge of any particular state.

So then because the system is deterministic, we know that if it returns to a previous state it must keep returning to this state forever?

> Forever: A time period that ranges from t=now to t=infinity.

Right, it’s a period of time, but the word “infinity” is not clarifying for me. Maybe, a period of time with no end?

>1. All physical systems must eventually halt.

In terms of physical computers I don't agree with must, but I will say there is a very high chance that it will. In terms of an arbitrary physical system something like gravity doesn't just halt.

>In many cases physical systems correspond to formal computational systems.

It is possible to model physical systems. It can also be useful to reason about a simplified model of something.

>So then because the system is deterministic, we know that if it returns to a previous state it must keep returning to this state forever?

Assuming it's deterministic then yes. Depending on how complicated your model is it may be hard to go back to a state you were in before.

>Maybe, a period of time with no end?

Sure.

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.

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

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.

Reply on news.ycombinator.com