Live data from Hacker News

Tetris is capable of universal computation

meatfighter.com

41–50 of 79 posts

Re: Tetris is capable of universal computation

#41

the claim is that this is theoretically possible in stock tetris with only one modification: an infinite board (with a floor). the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from…

You want to know how the Tetromino does memory allocation and garbage collection?

I don't think the infinite board is that big of a deal. Turing Machines and Lambda Calculus have no limits on their memory space and we implement analogues of them in our limited memory space.

Re: Tetris is capable of universal computation

#42

Just a note, this doesn't seem to create an isomorphism between _actively_playing_ with randomised figures, tetris. It just explains how one could create a turing machine based on controlled positioning of the figures. So essentially this is boring.

Agreed...if you have to introduce an "agent" to make it complete, is it Tetris that's complete or Tetris + an agent?

Re: Tetris is capable of universal computation

#43
post #34

Earlier quoted context omitted.

I am not sure that I understand your question. There are different models of computation [1] like Turing machines, finite state machines, lambda calculus or rewriting systems. A priori it could be possible that they all have different powers, that each of them is capable of solving different problems or requiring different amounts of resources like time and space to solve the same problem. But, as it turned out, this…

You know far more than I do. From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast . I guess the point I was trying to make is that even if CPUs only use a Turing-complete set of gates on the fine scale, the way they are arranged and connected (for things like massively parallel operations) is what set…

From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast.

This depends on how you want to understand fast. A Turing machine updates only a few bits per cycle while a modern computer easily updates many thousands if not millions of bits per cycle. Also a Turing machine access its memory very slowly because the head moves one cell per cycle, good luck reading a bit stored five gigabytes away from the current position of the head. So yes, in that sense a Turing machine is slow, especially random access memory is big advantage in practice, but in theoretic terms having to scan through the entire memory just gets swept under the rug of polynomial factors.

On the other hand you can build a Turing machine that emulates your modern computer even though it might need a trillion cycles to emulate just a single cycle of it. But mathematically you can just factor this out, you call a trillion cycles just one cycle and now both are the same speed, mathematically of course, not any physical implementation.

The other way that you allude to, using many Turing machines in parallel, is probably more realistic. You can probably build a small Turing machine with the equivalent of a few hundred or maybe few thousand gates. And you can program them to simulate a single logic gate in maybe ten or so cycles. Now rebuild you real computer with all gates replaced by those small Turing machines.

My gut feeling is that you could probably build a 80s or 90s era processor using current technology. A 1982 Intel 80286 has 134,000 transistors, that puts the number of gates well below 100,000 while a GeForce RTX 4090 has 16,384 shader cores which are way more powerful than our tiny Turing machine to simulate a single logic gate needs to be. So if you are willing to give up 30 years of Moore's law, you can probably have a Turing machine powered computer.

Heck [2], we have transistor level simulations of old processors [1], somebody with enough enthusiasm could probably do this at the gate level, then replacing gates with Turing machine simulations would be easy, and finally you would have to get them running on a GPU for decent speed, but I am not sure if GPUs would be any good for that kind of task, I have never programmed one. But this would be a processor running some code, simulated at the gate level with the gates implemented by Turing machines simulated on a real processor.

[1] http://visual6502.org/JSSim/index.html

[2] Is there any good replacement for heck, I think it has a negative connotation? But maybe stronger than look.

Re: Tetris is capable of universal computation

#45
post #18

It seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership selects for these articles. But is there any significance to be found in all these things having this attribute? Does it tell us anything about the universality of computation as a property of the universe? I seem to recall that sed and C++ template installati…

I guess the main takeaway is that you do not need much in order for something to be Turing-complete. On the other hand this should hardly be surprising, all you need is something to store a state and the ability to alter the state in a few different ways depending on the current state, and of course the ability to do this over and over again. The more surprising thing should maybe be that this is all you need and tha…

The only difference between a Turing machine and a finite state machine is that the Turing machine has a writeable tape with a movable head.

There is not much to it.

I think the deciding factor is that you can compose individual operations into new operations and use any previous result as input into the next computation.

Re: Tetris is capable of universal computation

#46

It seems like I quite often see posts here about how $thing$ can perform universal computation, or simulate a UTM, or whatever. And obviously the HN readership selects for these articles. But is there any significance to be found in all these things having this attribute? Does it tell us anything about the universality of computation as a property of the universe? I seem to recall that sed and C++ template installati…

Logic is fundamentally simple, and turning unexpected things into computational contraptions is fun.

Re: Tetris is capable of universal computation

#47
post #43

Earlier quoted context omitted.

You know far more than I do. From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast . I guess the point I was trying to make is that even if CPUs only use a Turing-complete set of gates on the fine scale, the way they are arranged and connected (for things like massively parallel operations) is what set…

From what little I understand the specialness of a Turing machine is that it can be used as a universal calculator, not that it can be used as a universal calculator fast. This depends on how you want to understand fast. A Turing machine updates only a few bits per cycle while a modern computer easily updates many thousands if not millions of bits per cycle. Also a Turing machine access its memory very slowly because…

When used as an intensifier heck, hell, and equivalents are fine. They lose the negative connotation as intensifiers. At least IMO.

Re: Tetris is capable of universal computation

#48

the claim is that this is theoretically possible in stock tetris with only one modification: an infinite board (with a floor). the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from…

> the infinite board solves piece randomization, because you can have a "junkyard" where you dump pieces until you get the one you want. it also solves the time pressure, because blocks spawned at row inifinity will never reach the canvas until you hard-drop them. finally, it prevents rows from clearing because they have infinite width (so the game won't interfere with your construction).

Not to mention that you need unbounded memory anyway.

Re: Tetris is capable of universal computation

#49
Here's something I wonder:

Imagine you're stuck on an island or in a forest, and you're stuck with what you find in nature only, or perhaps you get very primitive technology (e.g. basic metal working only):

What's the simplest way you could build some (mechanical) logic gates to do some form of useful computation?

I've seen some from lego or 3D printed ones, but they all look very complicated, e.g. requiring rubber bands or springs but not looking practical to combine many together in a useful circuit

Re: Tetris is capable of universal computation

#50

Here's something I wonder: Imagine you're stuck on an island or in a forest, and you're stuck with what you find in nature only, or perhaps you get very primitive technology (e.g. basic metal working only): What's the simplest way you could build some (mechanical) logic gates to do some form of useful computation? I've seen some from lego or 3D printed ones, but they all look very complicated, e.g. requiring rubber b…

relevant xkcd: https://xkcd.com/505/
Post reply on HN