Davis, Martin. Computability and Unsolvability. Dover (New York: 1958, 1973, 1982). ISBN 0-486-61471-9 pbk.
Last updated 2002-03-13-23:27 -0800 (pst)
- Algorithm or Effective Computational Procedure
- mechanical procedures by which the answers to any one of a class of questions can be obtained.
- Decision problem
- determining the existence of an algorithm for deciding the truth or falsity of a whole class of statements
- positive solution to a decision problem
- giving an algorithm for solving it
- negative solution to a decision problem
- showing that no algorithm for solving the problem exists
- unsolvable problem
- one for which there is a negative solution to the decision problem
- that a given formulation is an algorithm
- itself unsolvable
Suppose we generate all procedures in order of increasing length, and let E[i] be the ith procedure.
We will say that f[i](x) is the function that E[i] computes.
Now let g(x) = f[x](x)+1
For no value of i is it the case that g(x) = f[i](x).
Suppose that it was, then
there is some i0 such that g(x) = f[i0](x).
So f[i0](x) = f[x](x)+1 by definition of g(x)
and so it must also be true for x = i0,
f[i0](i0) = f[i0](i0)+1, which is a contradiction.
So no procedure in the E[i] has as its function, g(x). But all of the effective procedures are in E[i]. So g(x) is not effectively computable.
This establishes the existence of functions that are not effectively calculable. g(x) is not computable.
In the discussion of this result, Davis digs into how the the contradiction arises. The suspect is the supposition that one can create an enumeration of the effective procedures in the first place! (Sort of the Chinese Room flaw.) That is, the defect is in the hypothesized E[i].
Miser Note:
2000-08-09 (orcmid). It is also important to differentiate, here, the difference between the computable functions and the effective procedures. Notice that there may be many effective procedures for the same function. That is, there is no requirement that the correspondence be one-to-one. The other thing to notice is that the E[i], if they could be created, would be countable (the [i] assures that). So even if we made the P[i] be the set of procedures in some language (not necessarily ones corresponding to computable functions), the E are a subset of the P. It should be no surprise that there are far more functions than can be fit into that set, so there must be functions that are not computable by an argument on cardinality alone.
In coming up with a universal machine, there is something to pay attention to here. We want the P[i] that we arrive at to have all the E[i] that there can be (in the system of the given universal machine), and have them correspond to all the computable functions there are, with none missing.
Tuples are written like (3,2,7), with (1,2) for pairs. I would prefer [3,2,7] and [1,2] because I don't want to make any confusion with ordinary use of parentheses, especially for the arguments of functions. (See 3.3, below.)
Characteristic of n-tuples is that n-tuple identity is equivalent to identity of the corresponding elements.
Notation for general n-tuples is a kind of power notation that seems to be syntactical, using x(n) to mean x1,x2, ..., xn. It is not clear whether this is metalanguage or something else. There is also a tendency to write a tuple without the outer parentheses.
The fonts used for these are peculiar, and the convention seems to be a formal one. We may end up needing to restate this to deal with applicative notation and free-standing construction of tuples.
Uses membership, sets of n-tuples (for fixed n), and uses a simple subset symbol but does not mean proper subset. Empty set is symbolized by a little phi, ø, and the empty set is a subset of every set.
Miser Note: 2000-08-09 (orcmid) We need to do something about notation and HTML here. The Iverson solution for J does not seem acceptable. We want something that can translate well, but not require mathematical typography.
Notice that the empty set is simply a constant object, and we can use empty if need be. Or empty if that is more appropriate. It is important to avoid confusion with programming and formal examples. A sans-serif font might help, if we could count on it being available to people. Also, we need to avoid the presumption that we are using a programming notation.
For membership, we can have m member-of S, and in Frugal notation (not the language), we will have it be convenient to write is-member(m) S instead, to be read in the same sense.
For subsets, we can represent R included-in S by the notation is-included(R) S.
Similar translations lead to union(R) S, intersection(R) S, and complement R. Note that complement depends on knowing the universe of sets that we have in our hands. These functions are all defined on sets of n-tuples and the implicit domain is omitted. That is, we don't have to write complementn, but it needs to be understood in many contexts. (And empty is included in the domain and the range.)
Considers functions on n-tuples of natural numbers. That is how the n-tuple notation comes into play. Treats sets of n-tuples as domains, then functions on these domains to integers. So functions are defined on domains of n-tuples, with fixed n. These can be the Cartesian product on the Natural numbers, or they can be subsets of the Cartesians.
A function is total if its domain is the Cartesian.
division and subtraction are defined only on the natural numbers, so they have restricted domains.
The characteristic function of a set is a total n-ary function one that produces 0 if the argument n-tuple is a member of some set S, and 1 otherwise. This function is also called CS or, for Miser, C S.
Note the reversal from the usual sense of Boolean values. It doesn't matter of course, because one can make the dual of this function as well.
Does some cute things on C(union(R) S) = C(R) × C(S)
C(intersection(R) S) = C(R) + C(S) - C(R)×C(S)
C(complement R) = 1 - C(R)
It will be a matter of interest whether the characteristic function of a given set is computable. This is a way to formulate unsolvability.
2000-08-16: To be precise, as is our wont for Miser, we will probably have to make the order of a domain explicit, and so with the Characteristic Function of a set. This limitation is related to wanting to be very careful around enumeration and enumerability issues.
The propositional logic of statements assumes statements that assert propositions that must be either true or false. For statements, we have
p and q, p or q, and not p.
2000-08-16: It is important here that the propositions are about statements. That is, when we say that a statement "is" p and q, this can be taken as a semantic observation about the form (i.e., the sense) of a statement. It does not mean that the statement's literal expression is p and q. When we deal with formal logic, using propositional logic, we will look at is as if the sense-form is then all we have. However, there could be many interpretations of these forms in statements that do not resemble the sense-forms, but have agreed interpretations as such.
This is going to be important to us when we look at how language is dealt with in computational systems, and we look at the limitations that we employ to create a computational logic.
For now, it is important to understand that propositions in the form used in propositional algebra are the consequence of analysis of statements as to their sense. Then we apply propositional logic to arrive at new propositional forms that can be reinterpreted in natural language, where we preserve fixed senses of the constituent statements p, q, ... throughout. This is the sense in which propositional logic applies to statements.
2000-08-16: Predicates are viewed by Davis as having interpretations as statements upon substitution of particulars for its free variables. The predicate then becomes a (propositional) statement. We can examine whether what we have said, above, about sense-forms holds. In the example of P(x,y) being the predicate for the statement x = y + 3, it would seem to be so.
created 2000-08-09-08:00 -0700 (pdt) by orcmid
$$Author: Orcmid $
$$Date: 02-10-13 21:35 $
$$Revision: 10 $