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<[email protected]>
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 [email protected].
To unsubscribe from this group, send email to [email protected]
.
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
