Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tetris is capable of universal computation

meatfighter.com

Post reply on HN
Print view View original

11–20 of 79 posts

Re: Tetris is capable of universal computation

#11

Post by kykeonaut »

andyjohnson0 wrote: post #7

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…

Yes, you can indeed implement a Turing machine with DNA by modifying DNA strands to simulate Wang tiles; [0] this is modeled in the abstract self assembly model. [1] You can also build emojis with DNA. [2]

[0] https://thesis.library.caltech.edu/1866/1/winfree_thesis.pdf

[1] http://self-assembly.net/wiki/index.php?title=Abstract_Tile_...

[2] https://www.nature.com/articles/546687a

Re: Tetris is capable of universal computation

#13

Post by andyjohnson0 »

distcs wrote: post #10
andyjohnson0 wrote: post #7

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…

> But is there any significance to be found in all these things having this attribute? Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing?

> Is there any significance of a beautiful painting of a magnificent sunset over mountain meadow with horses grazing?

Yes, but it was designed that way. By a person. For other people. Its unlikely to be perceived as "beautiful" by a whale or an oak tree or whatever.

But if things that weren't designed to do computation, or even designed at all, nevertheless appear to be capable of it, what does that tell us about computation? Given that the fundamental physical behaviour of the universe can (maybe) be described computationally, is computation special in some way?

Re: Tetris is capable of universal computation

#14

Post by andyjohnson0 »

modarts wrote: post #8
andyjohnson0 wrote: post #7

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…

A sprawling read on the topic https://www.amazon.com/G%C3%B6del-Escher-Bach-Eternal-Golden...

Yep. I first read that when I was twelve. I wouldnt say I understood much back then, or even now after a number of re-readings. But its an amazing book. "Sprawling" is one word that I would use to describe it.

Re: Tetris is capable of universal computation

#16

Post by blauditore »

andyjohnson0 wrote: post #7

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…

Unlike the title suggests, the article/page is not a proof of Tetris' Turing completeness, but an actual implementation with UI and all. It's quite different from the other articles you're mentioning.

Re: Tetris is capable of universal computation

#17

Post by [deleted] »

andyjohnson0 wrote: post #7

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…

[deleted]

Re: Tetris is capable of universal computation

#18

Post by danbruc »

andyjohnson0 wrote: post #7

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 that adding more features does not buy you any additional power. Then again, having some state and being able to manipulate it conditionally is a very generic building block, what else could you possibly do? So maybe it should not even be that surprising that this is all you need.

Re: Tetris is capable of universal computation

#20

Post by woodrowbarlow »

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 clearing because they have infinite width (so the game won't interfere with your construction).

their concept for gates is that if you nudge a block at a certain row as it's falling, it will either shift one column over or be blocked. this page is a good visualization:

https://meatfighter.com/tetromino-computer/inverter-not.html

except... once you hard-drop a block in tetris, you can't nudge it. and if you don't hard-drop it, it will never reach your canvas.

they kind-of hand-wave this in the section "infinite playfield". after describing the mechanics of a hard drop, they say:

> A more generalized version, the semihard drop, attempts to vertically translate the piece from “row infinity” to a specified, finite row.

if the fall timer can't get the block into a finite row, how would a player (without hard-dropping)?

loved reading through this, though. the animations were perfect for describing the mechanism! very high-quality documentation for a fun project.

Post reply on HN