Re: Turing machine question

> 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


------------------------------------------------------------------------------
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