Turing Completeness in weird places
Moderators: phlip, Moderators General, Prelates
 Earlz
 Gets Obvious Implications
 Posts: 785
 Joined: Sat Jun 09, 2007 8:38 am UTC
 Location: USA
 Contact:
Turing Completeness in weird places
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?
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?
My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
DEFIANCE!
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Turing Completeness in weird places
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.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
Re: Turing Completeness in weird places
Someone's implemented Conway's Game of Life in LBP, which is Turing complete.
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.
 headprogrammingczar
 Posts: 3072
 Joined: Mon Oct 22, 2007 5:28 pm UTC
 Location: Beaming you up
Re: Turing Completeness in weird places
Minesweeper is Turing Complete. Some guy implemented all the logic gates, plus wires and wire crossings.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
 Earlz
 Gets Obvious Implications
 Posts: 785
 Joined: Sat Jun 09, 2007 8:38 am UTC
 Location: USA
 Contact:
Re: Turing Completeness in weird places
headprogrammingczar wrote:Minesweeper is Turing Complete. Some guy implemented all the logic gates, plus wires and wire crossings.
What? Minesweeper?
My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
DEFIANCE!
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
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 NPcomplete, though.
Useful page.
Normal minesweeper is NPcomplete, though.
Useful page.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 TheChewanater
 Posts: 1279
 Joined: Sat Aug 08, 2009 5:24 am UTC
 Location: lol why am I still wearing a Santa suit?
Re: Turing Completeness in weird places
I wonder if (a sufficiently tall) Tetris is Turingcomplete.
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.
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.
http://internetometer.com/give/4279
No one can agree how to count how many types of people there are. You could ask two people and get 10 different answers.
Re: Turing Completeness in weird places
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 Turingcomplete. Memory could possibly be done in a flipflop 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
 Posts: 979
 Joined: Sun Dec 27, 2009 12:28 am UTC
 Location: Ithaca, NY
Re: Turing Completeness in weird places
Æshættr wrote: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 Turingcomplete. Memory could possibly be done in a flipflop 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
The same as the old Meteorswarm, now with fewer posts!
Re: Turing Completeness in weird places
Meteorswarm wrote:Æshættr wrote: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 Turingcomplete. Memory could possibly be done in a flipflop 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?
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.
Re: Turing Completeness in weird places
fair enough.
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.
Re: Turing Completeness in weird places
My favroite is http://en.wikipedia.org/wiki/FRACTRAN
 Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.
 Berengal
 Superabacus Mystic of the First Rank
 Posts: 2707
 Joined: Thu May 24, 2007 5:51 am UTC
 Location: Bergen, Norway
 Contact:
Re: Turing Completeness in weird places
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, stopaslittleaspossible algorithm).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.
 sourmìlk
 If I can't complain, can I at least express my fear?
 Posts: 6393
 Joined: Mon Dec 22, 2008 10:53 pm UTC
 Location: permanently in the wrong
 Contact:
Re: Turing Completeness in weird places
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?
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?
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.
Re: Turing Completeness in weird places
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: Turing Completeness in weird places
WarDaft wrote: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.
Re: Turing Completeness in weird places
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 2tag 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.
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
So, like he said, abstract Minecraft (where the world is infinite in size, not limited to rounding errors, and you can build infinitesized 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).
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).
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Turing Completeness in weird places
Exactly. Viz:
WarDaft wrote:it's not TC because theredstonesilicon 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 2tag machine that computes the Collatz sequence for any integer, and I mean any integer, but you could never implement it fully inredstonea silicon chip as it stands now. If therewaswere ablocksilicon logic gate that could store arbitrary amounts of data, or you could create a contraption for laying down moreredstonesilicon circuitry and controlled by the circuitry itself, that would make it TC.
 sourmìlk
 If I can't complain, can I at least express my fear?
 Posts: 6393
 Joined: Mon Dec 22, 2008 10:53 pm UTC
 Location: permanently in the wrong
 Contact:
Re: Turing Completeness in weird places
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.
Is this repeated three times to echo the major general song?
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?
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.
Re: Turing Completeness in weird places
sourmìlk wrote: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.
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.So, like he said, abstract Minecraft (where the world is infinite in size, not limited to rounding errors, and you can build infinitesized 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).
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?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
WarDaft wrote: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 infinitelybig structures, you can easily make a machine that can calculate the busy beaver function just by hardcoding 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 t1, so to simulate it for a finite time, you only need to simulate a finite area), and it would still be TC...
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Turing Completeness in weird places
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.
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.
Last edited by WarDaft on Tue Feb 01, 2011 1:59 pm UTC, edited 1 time in total.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
WarDaft wrote:I think you'd have to restrict it to total computable functions
Well sure... I thought "total" was implied, unless "partial" is explicitly stated...
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Turing Completeness in weird places
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.
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
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 t1. So it's only dependent on a (31t)^{3}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.
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 t1. So it's only dependent on a (31t)^{3}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.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Turing Completeness in weird places
Each halting machine with a finite definition would only be a finite distance from some central reference point (only nonhalting 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.
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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 phlip
 Restorer of Worlds
 Posts: 7535
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Turing Completeness in weird places
WarDaft wrote:Each halting machine with a finite definition would only be a finite distance from some central reference point (only nonhalting 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 nonhalting 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;
}
WarDaft wrote: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 superTuring...
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Re: Turing Completeness in weird places
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.I'm not sure I'm reading you correctly, but are you basically saying that every halting program would eventually get reported, and nonhalting programs could be identified by it never being reported that they halt? This is nothing special, any TM can determine that:
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

 Posts: 778
 Joined: Mon Aug 11, 2008 10:58 pm UTC
 Location: Palo Alto, CA
Re: Turing Completeness in weird places
A video game running on (an approximation of) a turingcomplete system is not an interesting or surprising place to find turingcompleteness. You can't throw a rock at a computer without finding something turingcomplete.
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?
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?
GENERATION 16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.
Re: Turing Completeness in weird places
I was surprised to find that C++ was not one, but two Turingcomplete languages: C++ is, obviously, Turing complete, but the template metaprogramming syntax is also Turingcomplete. A side effect of this is that proving that an arbitrary C++ program is syntactically correct requires solving the halting problem.
 sourmìlk
 If I can't complain, can I at least express my fear?
 Posts: 6393
 Joined: Mon Dec 22, 2008 10:53 pm UTC
 Location: permanently in the wrong
 Contact:
Re: Turing Completeness in weird places
A video game running on (an approximation of) a turingcomplete system is not an interesting or surprising place to find turingcompleteness. You can't throw a rock at a computer without finding something turingcomplete.
A video game running on a turingcomplete system is not a difficult place to implement turingcompleteness, 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.
Terry Pratchett wrote:The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.
Who is online
Users browsing this forum: No registered users and 3 guests