Re: Turing machine question

> 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

------------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list