Accidentally Turing-Complete

https://beza1e1.tuxen.de/articles/accidentally_turing_complete.html

by ducaale • 4 years ago

85 48 4 years ago

beza1e1.tuxen.de

dane-pgp2• 4 years ago

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

stellaathena3• 4 years ago

This paper repeatedly states that it’s PSPACE, but I see no evidence that it’s Turing complete.

dane-pgp2• 4 years ago

Sorry, you're right, yes.

Technically, a problem is called PSPACE-complete if it is equal in computational power to a particular mathematical model of computation (called “polynomial-space-bounded Turing machines”).

alexb_• 4 years ago

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)

anyfoo• 4 years ago

I agree, that one is cheating. It appears that it's not the game that is Turing Complete in this case, it's the Gameboy itself. The Magic and Minecraft ones for example are legit, because "execution" happens within the game's engine (and, more importantly, rules).

LeoPanthera• 4 years ago

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

stellaathena3• 4 years ago

Tetris can be programmed on a computer, ergo anything that is Turing Complete can simulate Tetris. What am I missing?

simcop23872• 4 years ago

Computationally this is correct, however the tetris complete definition also sets requirements to interface with the outside world, in particular the timing and I outs aren't covered by turing completeness. a turing cokplete system could require villions of years to simulate a game of tetris and still be turing complete.

charcircuit5• 4 years ago

Tetris can be programmed on something that isn't Turing Complete.

grishka2• 4 years ago

Also there are things that are Doom Complete and Bad Apple Complete.

jwdunne• 4 years ago

Yeah, I was about to mention Doom. There’s a whole subreddit dedicated to running Doom on the weird and wonderful. Even had an eInk device running Doom, which looked painful but cool.

otabdeveloper4• 4 years ago

Anything that can recurse or fall into an infinite loop is Turing complete. (It's not a very interesting property.)

Much more interesting is what we can compute without Turing completeness.

(Shameless plug: https://tkatchev.bitbucket.io/tab/index.html)

charcircuit5• 4 years ago

Anything that can recurse or fall into an infinite loop is Turing complete.

My computer can fall into an infinite loop even though it doesn't have infinite storage (to emulate an infinite tape of a Turing machine).

newpavlov• 4 years ago

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.

saghm3• 4 years ago

Another fun Rust one I found was trying to make a macro to do arbitrary levels of `Option` flattening. There's an existing method `Option::flatten`, but it only flattens a single level (i.e. `Option<Option<T>>` to `Option<T>`, which makes sense given you can't really specify return type any differently. I had a hunch that it might be possible to do this by making a trait with a generic type parameter specifying that a given "flattening" is possible, e.g. `Option<Option<Option<T>>` would implement `Flatten<Option<Option<T>>` and `Flatten<Option<T>>`. This did turn out to be possible to specify with a couple of impl blocks; however, the compiler tried to exhaustively enumerate all of the possible implementations of this trait on all levels of `Option` nesting, whereas I had implicitly assumed it would just verify the correctness of the trait bounds that I used in my code. The compiler generated all the implementations of flatten for `Option<T>`, `Option<Option<T>>`, `Option<Option<Option<T>>>`...until it understandably hit a max recursion limit. Since the compiler obviously could not tell that there was no actual end to the implementations, it suggested that I try increasing the recursion limit with a crate-level attribute, and just for fun I followed its suggestions to keep increasing the limit to no avail, after which I took pity on the compiler and stopped forcing it to continue toiling in its Sisyphean endeavor.

exdsq• 4 years ago

Sort of reminds me of implementing multiplication in the type system of TypeScript with Peano arithmetic - endless recursion limit errors of Succ<Succ<Succ<Succ<Zero>>>>...

Never did get it to work properly :(

tialaramex2• 4 years ago

As you discovered, Rust's Generics aren't like a C++ template.

The C++ template really is just fill-in-the-blanks, (but with a special behaviour named SFINAE, Substitution Failure Is Not An Error) so I believe this trick would have worked if you'd been doing C++, producing all the necessary layers of flattening for whatever input you had.

To me, if I find that manually writing two more layers of flatten isn't enough, I would start to think this is the wrong problem to be solving.

dang• 4 years ago

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)

crabmusket2• 4 years ago

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.

taneq2• 4 years ago

Why is error correction seen as an exclusively digital thing? All sorts of things have error correction.

crabmusket2• 4 years ago

I believe Deutsch might argue that when error correction is implemented, a system becomes digital. Babbage's early computer, for example: "thus Babbage's computers assigned only ten different meanings to the whole continuum of angles at which a cogwheel might be oriented. Making the representation digital in that way allowed the cogs to carry out error-correction automatically"

What examples are you thinking of?

Dylan168073• 4 years ago

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.

grishka2• 4 years ago

Btw are CSS media expressions combined with CSS variables Turing-complete?

waynecochran2• 4 years ago

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.

LordRatte• 4 years ago

Do you have a reference explaining why two exactly?

waynecochran2• 4 years ago

Any textbook on formal languages and automata. Michael Sipser’s is my favorite. Church Turing Thesis is sophomore CS stuff..

Two stacks can simulate a Turing Tape. E.g. moving left is simulated by popping off one stack and pushing onto other. One counter can encode the tape while the other is used to encode the tape position.

DylanSp• 4 years ago

Oh cool, I didn't know there had been progress in the MtG UTM to use only mandatory effects.

Archelaos• 4 years ago

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

caf• 4 years ago

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

fjfaase• 4 years ago

Maybe it was not included, because John Conway suspected that it would be Turing complete from the start. Because he suspected this he contacted Martin Gardner and asked the public for searching for an ever growing pattern, resulting in the discovery of the glider gun. He realized that finding something like a glider gun would be the first step in establishing Turing Completeness. It took some time for it to be proven completely, but from the start the intuition of Conway was that Game of Life would probably be Turing Complete.

pfdietz• 4 years ago

This book on the engineering of mechanisms in Life is absolutely insane.

https://conwaylife.com/book/

DonHopkins• 4 years ago

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

YeGoblynQueenne• 4 years ago

> 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

Accidentally Turing-Complete

Related Stories