HackerTrans
TopNewTrendsCommentsPastAskShowJobs

zero__one

no profile record

Submissions

Lunar Explorer – A deep dive into a 1987 video game coded in BASIC

meatfighter.com
1 points·by zero__one·há 2 anos·0 comments

Tetris is capable of universal computation

meatfighter.com
199 points·by zero__one·há 4 anos·74 comments

comments

zero__one
·ano passado·discuss
The bug is fixed. Though you'll need to refresh the app to get the latest.
zero__one
·há 4 anos·discuss
Here is a list of Surprising Turing-complete things:

https://www.gwern.net/Turing-complete

Wang tiles are on the list. Are they Turing-complete by themselves? Or do they become Turing-complete only when an agent attempts to arrange them?
zero__one
·há 4 anos·discuss
There are several issues with that comic:

1. In finite time, it is not possible for a human to create an infinite row of rocks.

2. The academic paper for Rule 110 describes it as "weakly universal" rather than Turing-complete because it depends on an infinite pattern.

3. The rocks act as RAM, not the CPU. The human is applying the rules. The human is the CPU.

In the Tetris paper, the agent is just a TAS recording while Tetris acts as RAM and the CPU.
zero__one
·há 4 anos·discuss
The same idea appeared earlier on this page:

https://meatfighter.com/tetrisprinteralgorithm/
zero__one
·há 4 anos·discuss
For the method described in the paper to work, the infinite version of the game requires a semihard drop operation or something analogous as a legal move. In modern versions of Tetris, the rotation systems permit very unusual operations such as wall climbing or infinite lock delays, not to mention rotating in physically impossible ways. A semihard drop is not a big ask on an infinite playfield. It's within the spirit of the game.
zero__one
·há 4 anos·discuss
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.