On 30 Jan 2011, at 08:14, Brent Meeker wrote:

On 1/29/2011 10:41 PM, Rex Allen wrote:
On Sat, Jan 29, 2011 at 6:48 AM, Bruno Marchal<marc...@ulb.ac.be> wrote:

Rex,

Well here I disagree (with Wikipedia, not with Turing, although he is
responsible for this widespread misconception).

Well, I'll buy that, I reckon. Though the usage of the term "infinite
tape" is pretty widespread.  I see it lots of books, when I google
around.

Often they use infinite tape.  Less frequently, infinitely extensible
tape, or potentially infinite tape.

Infinite is usually in the mix somewhere.

Does their (and Turing's) use of the term "infinite tape" reflect an
actual difference of opinion?  Or just imprecise wording on their
part?  Or does it really make no difference, given that it's just an
abstract theoretical concept?


If the tape were finite, there'd be no halting problem.


That is not correct. You could as well say that, given that the math book are finite, there is no irrational numbers.

The no halting problem just says that given any universal number u and input k, we have no effective method (program) for knowing if (u k) will stop or, assuming we give to u memory when it asks for, not stop. It concerns finite machine, evolving in an unbounded environment. But during any execution the universal number will use a finite piece of the environment memory space.

The infinite tape is not part of the machine conceptually. Just accidentally in that definition. A universal machine is a number u such that phi_u(x,y) = phi_x(y), with phi_i an enumeration of the partial computable function. You can define 'universal number' in the arithmetical language.

Bruno






Brent

--
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/everything-list?hl=en .


http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Reply via email to