gdalgorithms-list

[Algorithms] Turing machine question

[Danny K. <dr...@we...>]

I've been making a small game about Turing machines, which features a
programmable robot that moves boxes around on a straight track, and I'm
wondering if anyone knows the answer to this question:

My robot works very similarly to a Turing machine, with one exception: it
can pick up and move boxes, but it can't create or destroy them. So if there
are 8 boxes on the track (equivalently, if there are 8 1's on the Turing
Machine tape), there will always be 8 boxes (one of which may be being
carried by the robot). Does anyone know if it's possible, given sufficient
boxes to work with, to make a universal TM using this system? My instinct
says no, but I'd be interested to know if the problem has been analysed or
has a name.

Thanks
Danny

Re: [Algorithms] Turing machine question

[Jon V. <ju...@gm...>]

This sounds pretty much like what you're talking about:
http://en.wikipedia.org/wiki/Linear_bounded_automaton

Good Luck!

Regards,
   Jon Valdés

On Thu, Jul 16, 2009 at 2:33 PM, Danny Kodicek<dr...@we...> wrote:
> I've been making a small game about Turing machines, which features a
> programmable robot that moves boxes around on a straight track, and I'm
> wondering if anyone knows the answer to this question:
>
> My robot works very similarly to a Turing machine, with one exception: it
> can pick up and move boxes, but it can't create or destroy them. So if there
> are 8 boxes on the track (equivalently, if there are 8 1's on the Turing
> Machine tape), there will always be 8 boxes (one of which may be being
> carried by the robot). Does anyone know if it's possible, given sufficient
> boxes to work with, to make a universal TM using this system? My instinct
> says no, but I'd be interested to know if the problem has been analysed or
> has a name.
>
> Thanks
> Danny
>
>
> ------------------------------------------------------------------------------
> Enter the BlackBerry Developer Challenge
> This is your chance to win up to $100,000 in prizes! For a limited time,
> vendors submitting new applications to BlackBerry App World(TM) will have
> the opportunity to enter the BlackBerry Developer Challenge. See full prize
> details at: http://p.sf.net/sfu/Challenge
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Turing machine question

[Fabian G. <f.g...@49...>]

> I've been making a small game about Turing machines, which features a
> programmable robot that moves boxes around on a straight track, and I'm
> wondering if anyone knows the answer to this question:
> 
> My robot works very similarly to a Turing machine, with one exception: it
> can pick up and move boxes, but it can't create or destroy them. So if there
> are 8 boxes on the track (equivalently, if there are 8 1's on the Turing
> Machine tape), there will always be 8 boxes (one of which may be being
> carried by the robot). Does anyone know if it's possible, given sufficient
> boxes to work with, to make a universal TM using this system? My instinct
> says no, but I'd be interested to know if the problem has been analysed or
> has a name.

Assuming that "box" corresponds to a 1 and "no box" corresponds to a 0 
on the tape, then no, you definitely can't; you can't even simulate an 
unbounded binary counter with that model! No matter how many boxes/bits 
you give it initially, at some point it will run out of bits... 
literally. Since this binary counter is a relatively simple TM, any UTM 
would have to be able to run it, so there can't be any UTM in this model.

This model seems closest to a linear bounded automaton, except it's 
deterministic. I don't think there's even any generally accepted name 
for this.

Cheers,
-Fabian "ryg" Giesen

Re: [Algorithms] Turing machine question

[Danny K. <dr...@we...>]

> Assuming that "box" corresponds to a 1 and "no box" 
> corresponds to a 0 
> on the tape, then no, you definitely can't; you can't even 
> simulate an 
> unbounded binary counter with that model! No matter how many 
> boxes/bits 
> you give it initially, at some point it will run out of bits... 
> literally.

I'm not sure it's quite that simple. The machine can definitely count, by
making a space between two boxes. If it wants to count to 5, all it needs is
to make 1000001. To multiply that number by 2, it can use a third box as a
placeholder, then double each space. There's a lot of computation that can
be done in that way. The number itself could have godel-numbered
instructions which might be possible to unpack and run in some clever way. I
agree that it feels like the domain is far too finite to be able to do
everything, but I don't think proving it would be quite so cut-and-dried.

 Danny

Re: [Algorithms] Turing machine question

[Fabian G. <f.g...@49...>]

> I'm not sure it's quite that simple. The machine can definitely count, by
> making a space between two boxes. If it wants to count to 5, all it needs is
> to make 1000001. To multiply that number by 2, it can use a third box as a
> placeholder, then double each space. There's a lot of computation that can
> be done in that way. The number itself could have godel-numbered
> instructions which might be possible to unpack and run in some clever way. I
> agree that it feels like the domain is far too finite to be able to do
> everything, but I don't think proving it would be quite so cut-and-dried.

To settle this, you'd need to define exactly what you mean by universality.

I'd state that a universal turing machine U is a TM that will, given a 
coded representation of another TM (let's call it M) and its input, 
produce the exact same output on the tape as running the original M with 
the given input directly if M halts on that input, if and only if M 
halts. And if M with the given input doesn't halt, then neither will U.

I'll further add the requirement that there be a fixed encoding for the 
TM input string; i.e. encoding a "0" or "1" input bit will always take 
the same amount of bits no matter where they are in the input string.

Expanding my example a bit: Assume a turing machine X that gets a binary 
number n as input, with the head initially just at right of the final 
digit. X will proceed to write exactly n ones starting at the initial 
head position, clear the rest of the tape to zero, and stop with the 
head at its initial position. This is a more precisely specified version 
of my binary counter example.

X is well-defined and will eventually halt on all inputs. Actually 
implementing X will involve some trickery such as padding the binary 
number somehow so that the start of the sequence of 1s can always be 
found, so it's not trivial, but it's not really complex either.

Now, X can be made to produce a string of 1s arbitrarily long given 
appropriate input. Doing a "left-shift" of n will only add a constant 
number of 1 bits (boxes), but double the number of "1" bits in the 
output. So you'll eventually run out of ones (boxes) for large enough n.

--

That's why I specifically mentioned a *binary* counter. If you allow 
arbitrary problem-specific transformations (like changing a binary into 
a unary counter), you can obviously work around the limitations for a 
lot longer, but you're not really executing the same algorithm.

I added the definition of universality (with the requirement of 
producing the same output, which is key here) to illustrate the point.

Kind regards,
-Fabian "ryg" Giesen

Re: [Algorithms] Turing machine question

[Jon W. <jw...@gm...>]

I thought that at first, too, but consider: Even if you represent 
numbers with spaces, you will run out of bits for the number of numbers 
that you'll need to represent. At most, you can represent (N-1) numbers 
with N available bits (and that doesn't take into account the 
book-keeping needed for applying any actual algorithm).

Sincerely,

jw


Danny Kodicek wrote:
>
> I'm not sure it's quite that simple. The machine can definitely count, by
> making a space between two boxes. If it wants to count to 5, all it needs is
> to make 1000001. To multiply that number by 2, it can use a third box as a
>   


-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Turing machine question

[Olivier G. <gal...@po...>]

On Thu, Jul 16, 2009 at 10:10:42AM -0700, Jon Watte wrote:
> I thought that at first, too, but consider: Even if you represent 
> numbers with spaces, you will run out of bits for the number of numbers 
> that you'll need to represent. At most, you can represent (N-1) numbers 
> with N available bits (and that doesn't take into account the 
> book-keeping needed for applying any actual algorithm).

Countable infinity is still countable infinity.  You can encode a set
of positive integers as
  N = 2**i1 * 3**i2 * 5**i3 * 7**i4 * 11**i5 * ...
which is only one number.  Alternatively you can encode the tape for a
turing machine as a number too.  If you call Ti the value of the bit
at position i relative to the head, you can encode the tape state as
  N = sum(Ti * 2**(i > 0 ? 2*i : i<0 ? -2*i-1 : 0))

If the tape wall all 0 at start, the number of non-zero Ti is finite
so there's no convergence issue.

In practice, you can encode any finite or countably infinite digital
system state in one number (that's where names like Godel start to
fuse).  So, on a turing-ish tape, that means two bits are enough.
Converting the program to run on the 1-bit limited version is the hard
part though.  I have no idea whether it's actually possible.

  OG.

Re: [Algorithms] Turing machine question

[Danny K. <dr...@we...>]

> In practice, you can encode any finite or countably infinite digital
> system state in one number (that's where names like Godel start to
> fuse).  So, on a turing-ish tape, that means two bits are enough.
> Converting the program to run on the 1-bit limited version is the hard
> part though.  I have no idea whether it's actually possible.

That's exactly where I was heading with the question, yes - thanks for 
reassuring me that I'm not being completely crazy. I envision a system where 
the distance between the first two boxes represents the simulated TM itself, 
the next distance represents its current state, the next represents the 
state of the tape, and the last represents the current position on the tape. 
(as you say you could further compress this into a single number, but that 
has the disadvantage that you have to do a lot more processing to work out 
what it's actually doing). Then any further calculations would be done with 
other boxes that come after these initial five. It seems to me that this 
ought to be doable with a finite number of boxes and a finite number of 
states, but I'm not sure.

I know it's a totally pointless and academic question, but it intrigues me 
strangely.

Danny