Xref: utzoo comp.ai:5522 talk.philosophy.misc:3428 sci.philosophy.tech:1910 Path: utzoo!attcan!uunet!cs.utexas.edu!usc!apple!ames!amdahl!kp From: kp@uts.amdahl.com (Ken Presting) Newsgroups: comp.ai,talk.philosophy.misc,sci.philosophy.tech Subject: Re: Algorithms, Turing, Semantics Summary: Explanation of the terms Message-ID: <91Eq02wy7eX=01@amdahl.uts.amdahl.com> Date: 13 Jan 90 21:32:27 GMT References: <12883@phoenix.Princeton.EDU> Reply-To: kp@amdahl.uts.amdahl.com (Ken Presting) Organization: Amdahl Corporation, Sunnyvale CA Lines: 112 In article <12883@phoenix.Princeton.EDU> kadickey@phoenix.Princeton.EDU (Kent Andrew Dickey) writes: > >I clearly must be missing something very important to all of these >discussions. Therefore, before I spew out my version of the world, I >have three questions: > >1) Could someone name one process which cannot be broken down into an >algorithm? That is, many people have said the mind may not be simulated >through an algorith, but personally, no other examples of >non-alogorithmical processes occur to me. Please, someone, tell me what >obvious example I'm missing. There has been a discussion here lately as to whether all processes are algorithmic, and some controversy perhaps remains. Algorithms are finite sets of rules determining transitions among a finite set of states. Physical systems usually have an infinite number of states, so any algorithm can at best approximate the behavior of a physical system. In a physical system with unstable components (where a small perturbation can produce large changes) the approximation may never be good enough. At least that is one point of view. Quantum mechanics comlicates the story, but doesn't seem to change the conclusion. I think there is some agreement that finitary algorithms are *different* in behavior from physical systems, and disagreement is only about the significance of the difference. Much more controversial is the question whether algorithms (or the tokens they manipulate) lack meaning. It is agreed that most symbol tokens in most algorithms can be assigned arbitrary meanings without changing the algorithm, and that therefore the algorithm is at least partly independent of meaning. Some infer that this makes algorithms different from thinking, which is waht the Chinese Room debate is all about. >2) Others have named that current computers are not Turing machines--is >this not false? Aren't all digital computer simulatable on a Turing >machine? Or again, am I missing something obvious? What's the simplest >problem a digital computer can solve that a Turing machine cannot? A guiding principle behind most of computer science is the "Church-Turing Thesis" - that all possible types of computation can be performed by Turing machines. Many formal systems for defining computations have been devised, and all can be reduced to Turing machine programs. The only difference between computers and Turing machines is: (1) Computers don't have an infinitely long tape (2) Computers are real physical objects, whereas Turing machines are abstract objects (like numbers or functions) >3) What is the definition of semantics? Before even attempting to >argue that syntax can give rise to semantics, I'd like to here some >definitions of what all of you think semantics mean. To me, semantics >is just a fancy term (aren't we all fond of using fancy terms) for >having a defined meaning--for example, that any time anyone in the >universe sees the word "telephone" they would think of a telephone, just >like any of us would :-). It seems that nothing in life, through this >loose, derived, definition, could ever have any semantics, so please, >someone define it for me before I post something I'll regret. The situation is not so bad as it sometimes appears, at least for the semantics of formal languages (ie mathematics or programs). Basically, the semantics of any language is a function from the words to objects and events. Syntax is a set of rules (ie a grammar for regular expressions) which defines which strings of symbols are in the language. Semantics has several parts: (1) a "model" which is a set of objects (perhaps the integers, or phsyical things) plus relations among those objects (such as {(x,y): x=y}). Usually properties (such as being an even number) are lumped in with realtions as a special case. (2) a "denotation function" which maps most of the symbols to objects and relations in the model (ie "1" |-> the smallest positive number) (3) "Truth conditions" for sentences (ie "a=b" is true if and only if the denotation of "a" = the denotation of "b") It is crucial that the truth conditions be defined recursively, so that the truth of a complex sentence can be determined from the truth of the parts, ie "apples are red and pears are green" is true when both parts are true. Meaning is the combination of denotation and truth conditions. Denotation is also called "reference". I've ignored issues of consciousness, intentions, and lots of others, because with even this simple type of semantics, lots of really horrible problems can be productively studied. This is a sketchy definition, but it's enough to see why the Chinese Room argument gets started. When Searle says that he "doesn't understand", he is saying that he doesn't know the denotation function and truth conditions for the Chinese sentences. Again, this is a sketchy reading of the Chinese room problem, and not the whole picture. But perhaps it's enough to get started. >As this post may indicate, I have something to say on each of these >topics, but wish to avoid the serious Net-gaffe and post something ill- >informed. I feel, however, that others may need the same clarification >as I, so I am posting this note first. Feel free to either post your >responses or send E-Mail, as I will summarize any replies I get. Thanks for asking. I have given my own opinions more prominence in this reply than they perhaps deserve, but I hope I've been fair to those who disagree. You might want to look up the article "The Semantic Conception of Truth" by Alfred Tarski, reprinted in several places including a collection edited by Leonard Linsky (I've forgotten the title). This is certainly the most famous paper ever written about semantics - Tarski shows how to solve the Liar paradox. Tarski was a fine writer and one of the great mathematicians of the century. Any fisrt-year logic texbook will have a better account of semantics than I've given above. I like Benson Mates "Elementary Logic", but that's just because it was my first logic text.