On Jan 23, 2010, at 5:08 PM, FERENC KOVACS 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