from Hacker News

Accidentally Turing-Complete

by ducaale on 2/3/22, 7:40 AM with 48 comments

by LeoPanthera on 2/5/22, 3:51 AM
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
by alexb_ on 2/5/22, 3:36 AM
It mentions Pokemon Yellow, but really any code run isn't really "run in the game" more so that it uses bugs to hack together alternate instructions for the game boy to execute. Good example: https://www.youtube.com/watch?v=Vjm8P8utT5g (skip to 1:20 for craziness)
by newpavlov on 2/5/22, 4:06 AM
Rust type system is also Turing complete: https://sdleffler.github.io/RustTypeSystemTuringComplete/
It has allowed us to emulate (numeric) const generics in crates like typenum (https://docs.rs/typenum) long before they were implemented as a proper language feature. Even today, typenum is more powerful in some regards than the stable version of const generics.
by YeGoblynQueenne on 2/5/22, 1:26 PM
>> Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem, solving a problem that has been open for a decade. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.
Nice, I didn't know of this one. It's the continuation and completion of work by the first author of the linked paper, Alex Churchill, who had earlier shown a method to prove M:tG Turing-Complete but in a setup that was not a full game:
https://www.toothycat.net/~hologram/Turing/HowItWorks.html
It's good to see he kept at it and seems to have produced a generally interesting result that applies well beyond M:tG, to boot. Wow.
Edit: Oh, shit. That means I'll never get funding to make an M:tG AI XD
by dang on 2/5/22, 4:08 AM
Past related:
Accidentally Turing-Complete - https://news.ycombinator.com/item?id=22964441 - April 2020 (58 comments)
A collection of things that are Turing-complete by accident (2013) - https://news.ycombinator.com/item?id=16383072 - Feb 2018 (63 comments)
Accidentally Turing Complete (2013) - https://news.ycombinator.com/item?id=9195519 - March 2015 (1 comment)
Accidentally Turing-Complete - https://news.ycombinator.com/item?id=6577671 - Oct 2013 (48 comments)
by waynecochran on 2/5/22, 5:12 AM
I don't think folks realize how low a bar Turing Complete is. A DFA with two stacks or two counters is Turing Complete. Making a formal machine Turing Complete is trivial.
by Archelaos on 2/5/22, 9:28 AM
"It inspired movfuscator, the single instruction C compiler. Building on this, there is a branchless, mov-only version of the classic DOOM video game.
This is thought to be entirely secure against the Meltdown and Spectre CPU vulnerabilities, which require speculative execution on branch instructions.
The mov-only DOOM renders approximately one frame every 7 hours, so playing this version requires somewhat increased patience."
This means, we need about twenty doublings of the computing speed to play it smoothly. Will we ever reach it? And if yes, when?
by dane-pgp on 2/5/22, 3:11 AM
One surprising example not listed there is "sliding-block puzzles", as proven in this paper:
https://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pd...
by Dylan16807 on 2/5/22, 4:57 AM
I continue to object to the CSS one, because it's just applying a couple gates / arithmetic operations at a time and you have to manually copy the data to the next iteration.
Turing completeness is already a low bar, because arithmetic+iteration is enough, and this doesn't clear the bar.
by crabmusket on 2/5/22, 4:47 AM
This reminds me of Deutsch's idea of the "jump to universality" in a chapter of The Beginning of Infinity. The summary:
> All knowledge growth is by incremental improvement, but in many fields there comes a point when one of the incremental improvements in a system of knowledge or technology causes a sudden increase in reach, making it a universal system in the relevant domain. In the past, innovators who brought about such a jump to universality had rarely been seeking it, but since the Enlightenment they have been, and universal explanations have been valued both for their own sake and for their usefulness. Because error-correction is essential in processes of potentially unlimited length, the jump to universality only ever happens in digital systems.
by caf on 2/5/22, 12:18 PM
One thing it doesn't mention is Conway's Game of Life itself.
So of course, you can implement Game of Life within Game of Life:
https://www.youtube.com/watch?v=xP5-iIeKXE8
by DylanSp on 2/5/22, 5:43 AM
Oh cool, I didn't know there had been progress in the MtG UTM to use only mandatory effects.
by DonHopkins on 2/5/22, 12:23 PM
I'll never regret asking this long-shot request on HN -- thanks to Harold Ancell and Marvin Minsky:
https://news.ycombinator.com/item?id=10161002
>DonHopkins on Sept 2, 2015 | parent | context | favorite | on: The most obsolete infrastructure money could buy –...
>I remember running across a Turing machine emulator implemented in TECO in Minsky's home directory that I'd REALLY love to get ahold of.
>hga on Sept 2, 2015 [–]
>Ask and yea shall receive:
```
    MSG: APL    1     
    DISTRIB:  *BBOARD
    EXPIRES: 03/17/81 23:08:54
    MINSKY@MIT-MC 03/11/81 23:08:54 Re: too-short programs

    APL is compact, I suppose.  So is TECO.  When I wrote the following
    Universal Turing Machine, which works, I actually understood it.

    [ I've interpolated the non-printing characters as displayed by (Gnu) EMACS, 
    escape is ^], ^^ is one character, as is \356: ]

    i1Aul qq+^^0:iqm^[29iiq\356y0L1 00L1 11L2 A1L1
    y0L1 0yR2 1AR2 AyR6 yyL3 00L0 1AL3 A1L4 yyL4 0yR5 11L7 A1L4
    yyR5 0yL3 1AR5 A1R5 yyR6 0AL3 1AR6 A1R6 y0R7 0yR6 11R7 A0R2
    ^[j<sR^[;-d-2ciql-^^^[ci"ed^^^[cii^[ciuq'^[>
    j<sL^[;-d-2ciql-^^^[ci"ed^^^[cii-2c^[ciuq'^[>jxblx1lx2lx3lx4lx5lx6lx7hk
    iyyAyyAyy^[32<i0^[>ji110101110000010011011^[ 1uq<htmbqq=>

    I do not advise attempting to understand this code, which is
    almost as bad as that for the Universal Turing machine.
```
>ADDED: or http://ancell-ent.com/share/minsky-TECO-turing-machine.txt
>Please ack receipt of this and/or send me email (in my HN info); for others, note this is ITS TECO, which I was told was by far the most powerful version of it (fortunately, by the time I showed up learning it was no longer really necessary).
>DonHopkins on Sept 3, 2015 | root | parent [–]
>OOP ACK! It was a shot in the dark, but I am SO GLAD I asked!!! Thank you Harold!
>It looks just like I remember. ;)
TECO eminently qualifies as a "Turing Tar Pit":
https://en.wikipedia.org/wiki/Turing_tarpit
>A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support for common tasks. The phrase was coined in 1982 by Alan Perlis in the Epigrams on Programming:
>>54. Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.
>In any Turing complete language, it is possible to write any computer program, so in a very rigorous sense nearly all programming languages are equally capable. Showing that theoretical ability is not the same as usefulness in practice, Turing tarpits are characterized by having a simple abstract machine that requires the user to deal with many details in the solution of a problem. At the extreme opposite are interfaces that can perform very complex tasks with little human intervention but become obsolete if requirements change slightly.
>Some esoteric programming languages, such as Brainfuck, are specifically referred to as "Turing tarpits" because they deliberately implement the minimum functionality necessary to be classified as Turing complete languages. Using such languages is a form of mathematical recreation: programmers can work out how to achieve basic programming constructs in an extremely difficult but mathematically Turing-equivalent language.
https://en.wikipedia.org/wiki/TECO_(text_editor)#As_a_progra...
>As a programming language: The obscurity of the TECO programming language is described in the following quote from "Real Programmers Don't Use Pascal", a letter from Ed Post to Datamation, July 1983:
>>It has been observed that a TECO command sequence more closely resembles transmission line noise than readable text. One of the more entertaining games to play with TECO is to type your name in as a command line and try to guess what it does. Just about any possible typing error while talking with TECO will probably destroy your program, or even worse - introduce subtle and mysterious bugs in a once working subroutine.
https://en.wikipedia.org/wiki/Real_Programmers_Don%27t_Use_P...
https://www.ee.ryerson.ca/~elf/hack/realmen.html