[Top] [All Lists]

Re: [ontolog-forum] can syntax be semantic

To: "[ontolog-forum] " <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Sat, 23 Jan 2010 18:34:46 -0600
Message-id: <F102FA3E-B720-4318-B498-D3B90D981EA3@xxxxxxxx>
On Jan 23, 2010, at 5:08 PM, FERENC KOVACS wrote:
Chris Menzel wrote
""AI representatives" no more have their own paradigm of the limits of computability than they have their own paradigm of what it is for a number to be prime.  Computability and (un)decidability are objectively defined concepts in mathematical logic and computer science and to demonstrate that a function is computable or that a problem is decidable or undecidable is (once again) no different in kind that proving that a given number is prime.  "Simple problem[s] of everyday experience" will typically not have any bearing on questions of computability and (un)decidability.  Of course, there might be analogies of these notions in everyday experience — but they are typically not going to be the same concepts."
I do not doubt that the above are objectively defined concepts. Yet with any concept that are created from verbs, or operations if you like, I have the suspicion that to compute or to decide are operations just as to add or to multiply, etc.

It's important to bear in mind that the idea of a Turing machine as a literal, functioning (albeit ideal) machine is just a heuristic aid.  Mathematically, a Turing machine M is typically just identified with its program (a set of 4- or 5-tuples, depending on the definition).  A computation by M is just a certain sequence of computation states, where a computation state consists simply of a natural number (representing the "internal" state of M at that point in the computation), a sequence of symbols (representing the content of the tape), and another natural number (representing the index of the cell being "scanned" by M).  In a computation by M, given an initial state S(0), each subsequence state S(n+1) is determined by S(n) and M's program.  A computation by M halts if the length of the computation is finite.  To say that Turing machine M computes a given 1-place (total) function f, then, is just to say (a bit roughly put) that, for any number n, f(n) = m iff there is a computation by M such that (i) the tape in the initial computation state S(0) represents n and (ii) the computation halts in a state in which the tape represents m.  (Typically, a number n is represented by a sequence of n+1 1s, so that we can represent 0 with a single 1.)

Thus, formally speaking, a computation is just a certain type of static mathematical object, a sequence.  Intuitively, the sequence represents the step-by-step computing process by the machine, but that is an intuitive idea only.  There is no notion of an operation or a process in any literal, dynamic sense.

Chris Menzel

Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (01)

<Prev in Thread] Current Thread [Next in Thread>