Path: utzoo!attcan!uunet!cme!kohout
From: kohout@cme.nist.gov (Robert Kohout)
Newsgroups: comp.ai
Subject: Re: Searle and Radical Translation (was: Re: Searle and Biology)
Summary: This is formal?
Message-ID: <5644@puggsly.cme.nist.gov>
Date: 7 Aug 90 15:22:36 GMT
References: <612@ntpdvp1.UUCP> <5362@puggsly.cme.nist.gov> <614@ntpdvp1.UUCP>
Organization: National Institute of Standards & Technology, Gaithersburg, MD
Lines: 82





To "formally" defend his assertion that "real" computers are "obviously"
more powerful that Turing Machines...

} In article <614@ntpdvp1.UUCP> kenp@ntpdvp1.UUCP (Ken Presting) writes:

} Some preliminaries:

<TM defined>

}TM's with unerased input tapes:
} 
} Not all paths in the state space of a machine begin with a configuration
} in standard form.  Let '|=' be a relation between paths in the state graph,
} defined as follows:
} 
}       <ss1,ss2> |= <ss1',ss2'>
}             iff
}          1. ss1 |-* ss2, and ss1' |-* ss2',
}          2. the TM halts in qf in ss2, and
}          3. there exists d, o, and i in S* such that
}             ss2 = d_qf_o, and ss1' = d_q0_i.
} 
} Thus, the '|=' relata can be compared to successive iterations of a
} program whose main loop waits for input (w1') synchronously, and maintains
} a "database" of some sort (w2).  The "database" is stored as a "tail" on
} the input and output tape configurations.
} 
} Since the TM is deterministic, the waiting state (if there is one) is a
} function of the initial state.  There is no difference in computing power
} due to the new arrangement of the tape - the difference is only notational.
} The obvious point is that the TM does not, in this notation, compute 'o'
} as a function of 'i'.
} 
Interesting, Ken, but what's the point? Do you intend to imply that this
relation represents something that computers "do" and Turing Machines don't?
Remember, non-determinism adds nothing to the computing power of a TM. If
a non-deterministic TM can compute a function, then there exists a deterministic
machine which can compute the same function.

} 
}       1.  A computer is used repeatedly to compute different values.
}       2.  The number of times a computer is used is unlimited in
}           principle.
}       3.  The device may modify its future operation in the course
}           of performing the current task.  (by updating the database)
}       4.  The sequence of values input to the computer cannot be
}           specified in advance.
} 
None of these are beyond the capacity of a Turing Machine.

} It may take a moment of thought to verify that while the set of paths
} for any TM is denumerable, the set of chains is not.
} 
Do you mean to imply by this that a computer is more powerful than a TM?
Do you REALLY think you are refuting Church's Thesis?

} The most important point here is that we should not suppose that by
} identifying computers with Universal Turing Machines we have said anything
} very specific about what they can and cannot do.  A Turing machine is a
} very flexible formalism.  Many familiar theorems about TM's refer only
} to a few of the many ways they can be employed.  Real computers implement
} the TM model in an especially powerful way.
} 
} 
This seems to me a sort of capitulation - that is, you no longer assert that
it is "perfectly obvious" that a conventional machine is more powerful than
a TM, but rather that "real" computers are "especially powerful" TM's. You
certainly haven't shown anything that computers "do" that TM's don't. For
that matter, you haven't made a single assertion about this |= relation
insofar as it applies to computers and not Turing Machines.

Why don't you just admit it Ken. What was "perfectly obvious" to you, is
just, plain wrong.

} Ken Presting  ("I only want to see my name in pixels")
  
R.Kohout