On Wed, Jul 19, 2006 at 02:11:28PM -0700, Andrew Lentvorski wrote:
> [EMAIL PROTECTED] wrote:
> >>Conceptually. Conceptually a physical thing. It isn't *really* a
> >>physical machine.
> >>
> >>In practice, you don't get an infinite tape to process, nor do you get
> >>an unbounded but finite time in which to do the computation.
> >
> >You don't need an infinite tape.
>
> Uh, no. You *do* need an infinite tape. In fact, I'm pretty sure that
> the proof of the halting problem is dependent upon this fact.
>
> BTW, Turing machines are not the only abstraction for computability.
> IIRC, Lambda Calculus was devloped for the same purpose and it was later
> proved that the two formulations are equivalent.
>
> -a
>
If they're equivalent, how does that demonstrate that Turing machines
are not the only abstraction for computability?
--
Lan Barnes
Linux Guy, SCM Specialist
Tcl/Tk Enthusiast
History, I believe, furnishes no example of a priest-ridden people
maintaining a free civil government. This marks the lowest grade of
ignorance of which their civil as well as religious leaders will always
avail themselves for their own purposes.
- Thomas Jefferson
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
