Path: utzoo!utgpu!attcan!uunet!husc6!cmcl2!nrl-cmf!mailrus!cornell!oravax!harper
From: harper@oravax.UUCP (Doug Harper)
Newsgroups: comp.misc
Subject: Re: What's a TM?
Summary: Is too strong a claim being made for DFSA's?
Message-ID: <435@oravax.UUCP>
Date: 4 Aug 88 21:38:12 GMT
References: <19918@cornell.UUCP> <934@netxcom.UUCP> <19965@cornell.UUCP>
Organization: Odyssey Research Ass., Ithaca NY
Lines: 22

In article <19965@cornell.UUCP>, blandy@lakshmi.cs.cornell.edu (Jim Blandy) writes:

>                                        A computer can do anything a TM
> can do, if one insists that the TM must halt and that the computer has
> sufficient memory.

Parsing English is always treacherous, but my first reading of the 
above can be semi-formalized as:

(1) There is a computer D, with a large memory, such that for any halting 
    TM computation C, D can perform C.

This is a bit too strong to be true.  No doubt, the intended parsing 
corresponds to:

(2) For any halting TM computation C, there is a computer D, with a
    large memory, such that D can perform C.
-- 
arpa:   oravax!harper@cu-arpa.cs.cornell.edu
uucp:   {allegra,rochester}!cornell!oravax!harper
Tel:    (607) 277-2020 ext. 257
USMail: Odyssey Research Associates/301A Harris B. Dates Dr./Ithaca, NY 14850