begin quoting [EMAIL PROTECTED] as of Wed, Jul 19, 2006 at 10:10:37PM -0700: [why was the attribution deleted?] > > >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. > > I'm just splitting hairs. In the real world if you ever tried to > build a physical device that simulated a Turing Machine you would > keep feeding it more tape as needed. Notice I didn't say that > you necessarily know how much finite tape you need beforehand.
Nor would you be certain of getting an answer to your computation before the heat-death of the universe. For trivial problems, you can use an approximation of a Turing Machine with a finite tape to demonstrate that yes, it can indeed compute. However, this is not what a Turing Machine is good for. -- _ |\_ \| -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-list
