begin quoting Andrew Lentvorski as of Wed, Jul 19, 2006 at 02:11:28PM -0700: > [EMAIL PROTECTED] wrote: > >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.
There's a whole bunch of formulations that are equivalent. The proof of equivalence is a cool sort of trick. It basically boils down to the idea that A and B are equivalent formulations if A can simulate A in a simulation of B (or A can simulate B and B can simulate A) -- _ |\_ \| -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
