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

31–40 of 79 posts

Re: Tetris is capable of universal computation

#31

Post by alexb_ »

UncleMeat wrote: post #23
adenozine wrote: post #6

Earlier quoted context omitted.

Suckerpinch is one of the best youtube channels out there, I love his work. I came here to link this once I saw the title, but you've already done it! He reminds me of what Forth people get so excited about, fitting so much into such small places.

If you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.

One of my favorites was an old one (I think 2013?) about "DollarCoin", a new cryptocurrency that is minted using a video of someone lighting a dollar bill on fire.

Re: Tetris is capable of universal computation

#32

Post by zero__one »

woodrowbarlow wrote: post #20

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…

From https://meatfighter.com/tetromino-computer/input-language.ht...

> In practice, IL programs direct the agent to construct a pile near the origin that progressively grows taller and wider. That being the case, it can work with a Tetris implementation that defines “row infinity” as a finite row whose index increases as a function of the number of spawns. In such an implementation, the agent emulates a semihard drop with a finite number of soft drops.

Re: Tetris is capable of universal computation

#33

Post by anonymouskimmer »

danbruc wrote: post #18
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 tha…

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

The "additional power" is what questions such as P-completeness and NP-completeness is about, right? Turing-completeness, as you say, is just a very minimal set of requirements on which additional requirements are added. Otherwise we'd all just be using massively parallel arithmetic calculators as our computers.

Re: Tetris is capable of universal computation

#34

Post by danbruc »

anonymouskimmer wrote: post #33
danbruc wrote: post #18

Earlier quoted context omitted.

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 more surprising thing should maybe be that this is all you need and that adding more features does not buy you any additional power." The "additional power" is what questions such as P-completeness and NP-completeness is about, right? Turing-completeness, as you say, is just a very minimal set of requirements on which additional requirements are added. Otherwise we'd all just be using massively parallel arithmet…

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 is not the case, within some polynomial factor they can all solve the same problems with the same amount of resources.

Only if you add some magical feature like an oracle that provides you in constant time the answer to an NP-complete problem, you get something more powerful than a Turing machine, at least as far as we know. There you get the difference between problems in P, that can be solved in polynomial time on a Turing machine, and problems in NP, that can be solved in polynomial time with the magic device but require exponential time on a Turing machine.

Quantum computers occupy a middle ground, as far as we know, they are more powerful than Turing machines but they are not magic. Using massively parallel computers is a trade-off between space and time - you need more silicon but less time, but in overall resources you are not any better off. In practice it might still matter, being able to predict the weather for tomorrow is much more useful if you can finish the calculation before tomorrow, so using more silicon and less time is a trade-off that gains you something. Also some technicalities apply, like Turing machines having an infinite amount of memory, but this does not really affect the larger picture.

[1] https://en.wikipedia.org/wiki/Model_of_computation

Re: Tetris is capable of universal computation

#35

Post by charcircuit »

Terris is officially defined by The Tetris Company to have a 10x40 playfield with 10x20 of it being visible. They do not allow for arbitrary sizes. If you have to change the game for it to be capable of universal computation then you shouldn't claim that the game is capable of it.

Re: Tetris is capable of universal computation

#36

Post by anonymouskimmer »

danbruc wrote: post #34
anonymouskimmer wrote: post #33

Earlier quoted context omitted.

"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." The "additional power" is what questions such as P-completeness and NP-completeness is about, right? Turing-completeness, as you say, is just a very minimal set of requirements on which additional requirements are added. Otherwise we'd all just be using massively parallel arithmet…

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 sets a modern CPU apart from a basic Turing machine. Allowing it more computational speed than an equivalent number of parallel basic Turing machines.

Re: Tetris is capable of universal computation

#37

Post by eouwt »

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…

Imho the fact that a Turing machine is capable of universal computation is surprising/insightful. I'm not sure the fact that other simple systems are then also complete adds much more surprise/insight, even if it's difficult to predict which ones will be.

What I think people often miss is the difference between computational completeness and computational "power". Yes rule 110 is complete, but what that means in practice is that you've shifted most of the work (for solving a real problem) onto specifying the initial conditions.

Maybe Tetris is Turing complete but it's still a lot easier to compute 2+2 on a pocket calculator.

Re: Tetris is capable of universal computation

#38

Post by woodrowbarlow »

zero__one wrote: post #32
woodrowbarlow wrote: post #20

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…

From https://meatfighter.com/tetromino-computer/input-language.ht... > In practice, IL programs direct the agent to construct a pile near the origin that progressively grows taller and wider. That being the case, it can work with a Tetris implementation that defines “row infinity” as a finite row whose index increases as a function of the number of spawns. In such an implementation, the agent emulates a semihard drop…

that's not really infinite, though, and other pages do describe it as truly infinite, e.g.:

> When a newly spawned piece falls, it never gets closer to the floor due to the nature of infinity.

i'm nitpicking, of course. everything described is possible with a sufficiently large board. you'll just have a time constraint to place each block.

Re: Tetris is capable of universal computation

#39

Post by EvanAnderson »

adenozine wrote: post #6
askiiart wrote: post #3

As for Tetris storage, see also: Harder Drives - https://youtu.be/JcJSW7Rprio The Tetris part starts at 15:00, but I'd highly recommend watching it all.

Suckerpinch is one of the best youtube channels out there, I love his work. I came here to link this once I saw the title, but you've already done it! He reminds me of what Forth people get so excited about, fitting so much into such small places.

Came here to post this myself, too. Tom7 is a treasure.

Re: Tetris is capable of universal computation

#40

Post by dado3212 »

UncleMeat wrote: post #23
adenozine wrote: post #6

Earlier quoted context omitted.

Suckerpinch is one of the best youtube channels out there, I love his work. I came here to link this once I saw the title, but you've already done it! He reminds me of what Forth people get so excited about, fitting so much into such small places.

If you like his stuff you should check out the sigbovik proceedings each year. Most of his videos are about his papers there and he has even more papers he doesn't make videos about! I don't think anybody else is making papers as interesting as his (about half are just jokes with no real content) but there are other gems of a similar "work hard on a fundamentally silly problem" vein.

Is there an easy way to look all of them up?
Post reply on HN