Turing Completeness in weird places

[Earlz]

So I was playing Little Big Planet and I saw a custom made level that implemented a calculator capable of adding and subtracting 2 digit numbers.

If this machine somehow implemented a Turing complete calculator, would that mean that Little Big Planet's object/physics engine is Turing complete? What about other similar things where you can build things. How can you easily prove them to be Turing complete?

[Berengal]

Turing complete systems (or rather, FSMs) are all around us. The easiest way of proving that they are is to implement a previously known turing complete system in them, e.g. a universal turing machine, or the lambda calculus, or brainfuck. As for LBP there's this already. I don't know if that particular machine's a UTM, but the surrounding framework certainly looks like it could hold one.

[Sizik]

Someone's implemented Conway's Game of Life in LBP, which is Turing complete.

[headprogrammingczar]

Minesweeper is Turing Complete. Some guy implemented all the logic gates, plus wires and wire crossings.

[Earlz]

Minesweeper is Turing Complete. Some guy implemented all the logic gates, plus wires and wire crossings.

What? Minesweeper?

[phlip]

Well, a generalised version of Minesweeper, with an infinite grid, and a generalised set of restrictions (normal Minesweeper has restrictions like "a 4 must be surrounded by exactly 4 bombs", but this generalised one can have things like "an A must be surrounded by exactly 4 B's, and each B must be surrounded by exactly 2 C's" or whatever).

Normal minesweeper is NP-complete, though.

Useful page.

[TheChewanater]

I wonder if (a sufficiently tall) Tetris is Turing-complete.

The input is the order the tetrominos fall and to where, and (although I can't prove it) I'm guessing you could compute anything, with the output being the final state.

[Æshættr]

There are examples of building computing fortresses in Dwarf Fortress. It's a bit of a daunting task to actually build a dwarfputer, and as far as I know, nobody has proven it to be Turing-complete. Memory could possibly be done in a flip-flop fashion with many wells of water and pressure plates. Logic gates have already been done, as have several methods of a clock signal (link.)

[Meteorswarm]

There are examples of building computing fortresses in Dwarf Fortress. It's a bit of a daunting task to actually build a dwarfputer, and as far as I know, nobody has proven it to be Turing-complete. Memory could possibly be done in a flip-flop fashion with many wells of water and pressure plates. Logic gates have already been done, as have several methods of a clock signal (link.)

You could prove it to be Turing complete by implementing a game of life simulator. It wouldn't be that hard to do for a few cells, and that's all you'd need for the proof. Game of life is Turing complete (although, similar to DF, in a horrifically annoying way), so therefore DF is Turing complete

[Josephine]

There are examples of building computing fortresses in Dwarf Fortress. It's a bit of a daunting task to actually build a dwarfputer, and as far as I know, nobody has proven it to be Turing-complete. Memory could possibly be done in a flip-flop fashion with many wells of water and pressure plates. Logic gates have already been done, as have several methods of a clock signal (link.)

You could prove it to be Turing complete by implementing a game of life simulator. It wouldn't be that hard to do for a few cells, and that's all you'd need for the proof. Game of life is Turing complete (although, similar to DF, in a horrifically annoying way), so therefore DF is Turing complete

Is there nothing Dwarf Fortress cannot do?

[b.i.o]

Is there nothing Dwarf Fortress cannot do?

There are a few.

[Josephine]

Is there nothing Dwarf Fortress cannot do?

There are a few.

fair enough.

[Macbi]

My favroite is http://en.wikipedia.org/wiki/FRACTRAN

[Berengal]

Indeed, FRACTRAN is one of my favorites as well. It was one of the languages that helped me the most in grokking turing completeness. After learning how it worked I was constantly identifying universal machines everywhere, like a pair of roundabouts I drive through on the way to work (provided drivers always follow a greedy, stop-as-little-as-possible algorithm).

[sourmìlk]

I am bumping this thread.

I believe that minecraft is turing complete. I've created little combination locks and such using logic gates, and one person even built a 32 bit ALU (http://www.youtube.com/watch?v=MMW_jraSjq8).

My understanding of the term "turing complete" is sketchy, but does the existence of logic gates in a system necessitate turing completeness?

[WarDaft]

Minecraft is not Turing Complete, just like a real computer is not Turing Complete. Given a method for storing arbitrarily large amounts of data and it would be, but the amount of storage your program has is built into its 'source code' per se.

[letterX]

Minecraft is not Turing Complete, just like a real computer is not Turing Complete. Given a method for storing arbitrarily large amounts of data and it would be, but the amount of storage your program has is built into its 'source code' per se.

Oh, well then. Guess nothing is really Turing Complete, then, so it's a useless term.

Anyways, abstract Minecraft is definitely TC.

grumblegrumble... goes and finds a computer which can play abstract Minecraft.

[WarDaft]

No, I don't mean it's not TC because the computer isn't TC, I mean it's not TC because the redstone circuits have a built in maximum amount of data they can store. As it stands, no design would be sufficient to compute any function across unbounded input, which TC languages can. There is an extremely simple 2-tag machine that computes the Collatz sequence for any integer, and I mean any integer, but you could never implement it fully in redstone as it stands now. If there was a block that could store arbitrary amounts of data, or you could create a contraption for laying down more redstone circuitry and controlled by the circuitry itself, that would make it TC.

A language can still be Turing Complete even if the hardware we have available to run it is not, but current redstone technologies do not qualify.

[phlip]

So, like he said, abstract Minecraft (where the world is infinite in size, not limited to rounding errors, and you can build infinite-sized structures within it, and the game doesn't unload bits of the level far away from the player for optimisation reasons, but instead simulates the entire world) would be TC.

In exactly the same way as how an abstract computer is TC, but a real computer isn't (due to limited RAM, limited address space, etc). I don't see any fundamental difference between the fact that Minecraft only simulates a certain area of the map, and your circuit has to fit (thus limiting its size) and the fact that an x86 only has so much RAM, and, even theoretically, can only be expanded to have 4GB of RAM. Both are mere technical limitations which can be expanded easily enough (and can be considered unbounded in the abstract).

[letterX]

Exactly. Viz:

it's not TC because the redstone silicon circuits have a built in maximum amount of data they can store. As it stands, no design would be sufficient to compute any function across unbounded input, which TC languages can. There is an extremely simple 2-tag machine that computes the Collatz sequence for any integer, and I mean any integer, but you could never implement it fully in redstone a silicon chip as it stands now. If there was were a block silicon logic gate that could store arbitrary amounts of data, or you could create a contraption for laying down more redstone silicon circuitry and controlled by the circuitry itself, that would make it TC.

[sourmìlk]

You guys are awesome.

And yes, I thought it was assumed that, given infinite resources, it's turing complete. If we're not making that assumption, then nothing is, and this discussion is pointless.

His chances for survival shrank from small to infinitesimal.
His chances for survival shrank from small to infinitesimal.
His chances for survival shrank from small to infinitesimal!

Is this repeated three times to echo the major general song?

[WarDaft]

Is this repeated three times to echo the major general song?

Technically, yes, but I was not the one to repeat it. It's from the ReBoot recap song, which is to the tune of the Modern Major General. Being a recap song, it has major spoilers in it.

So, like he said, abstract Minecraft (where the world is infinite in size, not limited to rounding errors, and you can build infinite-sized structures within it, and the game doesn't unload bits of the level far away from the player for optimisation reasons, but instead simulates the entire world) would be TC.

In exactly the same way as how an abstract computer is TC, but a real computer isn't (due to limited RAM, limited address space, etc). I don't see any fundamental difference between the fact that Minecraft only simulates a certain area of the map, and your circuit has to fit (thus limiting its size) and the fact that an x86 only has so much RAM, and, even theoretically, can only be expanded to have 4GB of RAM. Both are mere technical limitations which can be expanded easily enough (and can be considered unbounded in the abstract).

Actually, now that you mention things like address space, is an infinite amount of RAM what we would even want? What we need to give it is an infinite redstone tape (which could definitely be built with existing redstone circuit patterns), just like a Turing machine, so that the program can store arbitrary amounts of data without needing infinitely large access methods, instead having just left/right/read/write. So, yes, I suppose Abstract MineCraft with an infinite redstone tape in it is TC.

Building infinitely large structures though... isn't that treading a little close to the infinite state Turing machine, which is equivalent to an oracle machine?

[phlip]

Building infinitely large structures though... isn't that treading a little close to the infinite state Turing machine, which is equivalent to an oracle machine?

Hmm, you have a point... you'd have to be careful defining it. Just making infinitely-big structures, you can easily make a machine that can calculate the busy beaver function just by hard-coding a full mapping table...

I think that if you define an infinite structure as a computable function f:Z×Z×Z→Block data, then a TM could simulate it (the state of a given block at time t is only dependent on the blocks within a finite area at time t-1, so to simulate it for a finite time, you only need to simulate a finite area), and it would still be TC...

[WarDaft]

I think you'd have to restrict it to total computable functions, else you could simply have a computable function which simulates a TM encoded by block location to see if it halts, then you'd either be left with a lot of undefined blocks, or oracle blocks. I *think* that would do it, so that each block has a well defined value that- wait, no, that's not enough either, unless we're presuming that the abstraction has to manually calculate the play field as well.

In either case, I think it's simpler just to presume the existence of a special infinite redstone tape with a virtual head that reports back to a fixed position 'cpu' managing your program.

I suddenly feel this strange compulsion to play with some redstone.

[phlip]

I think you'd have to restrict it to total computable functions

Well sure... I thought "total" was implied, unless "partial" is explicitly stated...

[WarDaft]

Even then, I'm not sure it's enough, unless the play field is still being constructed as the abstracted program runs, and is not required to achieve it's final state before the redstone program interacts with a given block.

Otherwise, we could create a total computable function that creates a play field which is not fully defined until infinitely many values of the function has been completed - specifically, rather than each block checking if a TM has halted, each block checks if a TM has halted by a given step, and has a redstone circuit beside it to transmit back the information if one of the blocks in the chain finds that yes the TM has indeed halted at some finite step.

[phlip]

But that redstone circuit to transmit the information back would take infinite time to run, as it would have to cover infinite distance, and a redstone signal can only travel 15m per tick...

Hence what I said about the state of a given block at time t only being dependent on a finite area (a 31x31x31m volume around the bock at absolute maximum) of the state at time t-1. So it's only dependent on a (31t)³-block volume of the original state at time 0, so that's all you need to simulate. And then to simulate the next tick, you can just start again with a bigger chunk of the original state. Would be massively inefficient, but would be accurate and complete.

[WarDaft]

Each halting machine with a finite definition would only be a finite distance from some central reference point (only non-halting functions would have infinitely long redstone circuits assigned to them as the answer would always be "no" for "has it halted yet?") meaning that eventually for each halting function a signal could get back to your CPU, and that you necessarily have to run the program within the world itself before everything in the world has reached its final state.

On the other hand, we can create a simple pattern to represent an infinite tape and just tessellate it to give the redstone CPU everything it needs to be TC. I'm actually working on it right now.

[phlip]

Each halting machine with a finite definition would only be a finite distance from some central reference point (only non-halting functions would have infinitely long redstone circuits assigned to them as the answer would always be "no" for "has it halted yet?") meaning that eventually for each halting function a signal could get back to your CPU, and that you necessarily have to run the program within the world itself before everything in the world has reached its final state.

I'm not sure I'm reading you correctly, but are you basically saying that every halting program would eventually get reported, and non-halting programs could be identified by it never being reported that they halt? This is nothing special, any TM can determine that:

Code: Select all

bool halts(func,input)
{
  func(input);
  return true;
}

On the other hand, we can create a simple pattern to represent an infinite tape and just tessellate it to give the redstone CPU everything it needs to be TC. I'm actually working on it right now.

Well sure, I'm not claiming my formulation is necessary for it to be TC... just that it's a natural abstraction of the Minecraft world, which is TC and (I think) sufficiently restricted to not be super-Turing...

[WarDaft]

I'm not sure I'm reading you correctly, but are you basically saying that every halting program would eventually get reported, and non-halting programs could be identified by it never being reported that they halt? This is nothing special, any TM can determine that:

Vaguely... I'm saying you either have to accept running redstone programs in an environment that may at some point change the redstone state in a way totally unrelated to the redstone program, or compute the whole environment beforehand which can result in an oracle.

[stephentyrone]

A video game running on (an approximation of) a turing-complete system is not an interesting or surprising place to find turing-completeness. You can't throw a rock at a computer without finding something turing-complete.

Human heart tissue was a surprising place to find (possible) turing completeness. (I say "possible" because the article in which it was reported was not exactly a magnum opus of science writing).

Other interesting examples of (possibly) turing completeness in places that are not obviously computational systems?

[Carnildo]

I was surprised to find that C++ was not one, but two Turing-complete languages: C++ is, obviously, Turing complete, but the template metaprogramming syntax is also Turing-complete. A side effect of this is that proving that an arbitrary C++ program is syntactically correct requires solving the halting problem.

[sourmìlk]

A video game running on (an approximation of) a turing-complete system is not an interesting or surprising place to find turing-completeness. You can't throw a rock at a computer without finding something turing-complete.

A video game running on a turing-complete system is not a difficult place to implement turing-completeness, but a game created for entertainment is still an interesting place to find it. I'm not aware of very many games (except in very specific genres) that are really turing complete.