Turing Completeness in weird places

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Turing Completeness in weird places

Postby Earlz » Sun Feb 28, 2010 7:32 am UTC

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?
My new blag(WIP, so yes it's still ugly..)
DEFIANCE!
Image
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
User avatar
Earlz
Gets Obvious Implications
 
Posts: 786
Joined: Sat Jun 09, 2007 8:38 am UTC
Location: USA

Re: Turing Completeness in weird places

Postby Berengal » Sun Feb 28, 2010 1:04 pm UTC

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.
User avatar
Berengal
Superabacus Mystic of the First Rank
 
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

Re: Turing Completeness in weird places

Postby Sizik » Sun Feb 28, 2010 5:58 pm UTC

Someone's implemented Conway's Game of Life in LBP, which is Turing complete.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.
User avatar
Sizik
 
Posts: 835
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Turing Completeness in weird places

Postby headprogrammingczar » Sun Feb 28, 2010 8:57 pm UTC

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
User avatar
headprogrammingczar
 
Posts: 3025
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Turing Completeness in weird places

Postby Earlz » Mon Mar 01, 2010 7:05 am UTC

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!
Image
This is microtext. Zooming in digitally makes it worse. Get a magnifying glass.. works only on LCD
User avatar
Earlz
Gets Obvious Implications
 
Posts: 786
Joined: Sat Jun 09, 2007 8:38 am UTC
Location: USA

Re: Turing Completeness in weird places

Postby phlip » Mon Mar 01, 2010 7:31 am UTC

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.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby TheChewanater » Sat Mar 27, 2010 3:50 am UTC

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.
ImageImage
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.
User avatar
TheChewanater
 
Posts: 1286
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

Postby Æshættr » Sat Mar 27, 2010 9:23 pm UTC

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.)
User avatar
Æshættr
 
Posts: 149
Joined: Mon Jul 30, 2007 4:47 am UTC

Re: Turing Completeness in weird places

Postby Meteorswarm » Sun Mar 28, 2010 4:19 pm UTC

Æ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 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
The same as the old Meteorswarm, now with fewer posts!
User avatar
Meteorswarm
 
Posts: 980
Joined: Sun Dec 27, 2009 12:28 am UTC
Location: Ithaca, NY

Re: Turing Completeness in weird places

Postby Josephine » Sun Mar 28, 2010 6:18 pm UTC

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 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?
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.
User avatar
Josephine
 
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: Turing Completeness in weird places

Postby b.i.o » Sun Mar 28, 2010 7:58 pm UTC

nbonaparte wrote:Is there nothing Dwarf Fortress cannot do?

There are a few.
User avatar
b.i.o
Green is the loneliest number
 
Posts: 2520
Joined: Fri Jul 27, 2007 4:38 pm UTC
Location: Hong Kong

Re: Turing Completeness in weird places

Postby Josephine » Sun Mar 28, 2010 9:20 pm UTC

b.i.o wrote:
nbonaparte wrote:Is there nothing Dwarf Fortress cannot do?

There are a few.

fair enough.
Belial wrote:Listen, what I'm saying is that he committed a felony with a zoo animal.
User avatar
Josephine
 
Posts: 2142
Joined: Wed Apr 08, 2009 5:53 am UTC

Re: Turing Completeness in weird places

Postby Macbi » Tue Mar 30, 2010 4:23 pm UTC

    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.
User avatar
Macbi
 
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

Re: Turing Completeness in weird places

Postby Berengal » Tue Mar 30, 2010 4:55 pm UTC

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).
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.
User avatar
Berengal
Superabacus Mystic of the First Rank
 
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway

Re: Turing Completeness in weird places

Postby sourmìlk » Tue Feb 01, 2011 5:26 am UTC

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?
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.
User avatar
sourmìlk
If I can't complain, can I at least express my fear?
 
Posts: 6407
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 6:27 am UTC

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.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby letterX » Tue Feb 01, 2011 6:47 am UTC

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.
letterX
 
Posts: 529
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 6:54 am UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby phlip » Tue Feb 01, 2011 7:15 am UTC

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).
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby letterX » Tue Feb 01, 2011 7:32 am UTC

Exactly. Viz:
WarDaft wrote: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.
letterX
 
Posts: 529
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Turing Completeness in weird places

Postby sourmìlk » Tue Feb 01, 2011 9:10 am UTC

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?
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.
User avatar
sourmìlk
If I can't complain, can I at least express my fear?
 
Posts: 6407
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 10:08 am UTC

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.

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?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby phlip » Tue Feb 01, 2011 10:33 am UTC

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 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...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 1:54 pm UTC

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.
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.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby phlip » Tue Feb 01, 2011 1:57 pm UTC

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...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 2:05 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby phlip » Tue Feb 01, 2011 2:17 pm UTC

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)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.
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 2:26 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby phlip » Tue Feb 01, 2011 10:15 pm UTC

WarDaft wrote: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;
}


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 super-Turing...
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7203
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Turing Completeness in weird places

Postby WarDaft » Tue Feb 01, 2011 10:25 pm UTC

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.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Turing Completeness in weird places

Postby stephentyrone » Wed Feb 02, 2011 7:51 pm UTC

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?
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.
stephentyrone
 
Posts: 779
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Turing Completeness in weird places

Postby Carnildo » Thu Feb 03, 2011 4:09 am UTC

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.
Carnildo
 
Posts: 2022
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Turing Completeness in weird places

Postby sourmìlk » Thu Feb 03, 2011 2:59 pm UTC

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.
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.
User avatar
sourmìlk
If I can't complain, can I at least express my fear?
 
Posts: 6407
Joined: Mon Dec 22, 2008 10:53 pm UTC
Location: permanently in the wrong


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 4 guests