Bibliography Readings/Notes
Computation Theory Definitions, Nomenclature,
and Elementary Concepts
|
|
Bibliography Readings/Notes |
The Introduction (Chapter 0) of [Sipser1997] covers prerequisites to computation theory. These notes work up to the exercises and problems of the introduction. My attention is on extracting a consistent nomenclature (Frugalese) and mathematical precepts for development of Miser and for application of the Miser Project to demonstration of key elements of computation theory.
This 2001 material is deficient, in that it does not rely on Sipser so much as my notes from [Davis1982] at r000800. The editing from that as boilerplate with an account of the Sipser coverage is apparently incomplete. My ideas for Frugalese have probably advanced farther than the indications here, as well. I do not expect to develop this particular note any further. This page is preserved for reference and historical purposes.
-- Dennis E. Hamilton
Seattle, Washington
2014-05-03
References
- 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
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.
 |
You are navigating Orcmid on GitHub |
created 2001-09-08T00:19Z by orcmid |
