Miser Project Readings 
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
20140503
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 ntuples is that ntuple identity is equivalent to identity of the corresponding elements.
Notation for general ntuples is a kind of power notation that seems to be syntactical, using x^{(n)} to mean x_{1},x_{2}, ..., x_{n}. 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 freestanding construction of tuples.
Uses membership, sets of ntuples (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: 20000809 (orcmid) We need to do something about notation and HTML here. The Iverson solution for J does nto 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 sansserif 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 memberof S, and in Frugal notation (not the language), we will have it be convenient to write ismember(m) S instead, to be read in the same sense.
For subsets, we can represent R includedin S by the notation isincluded(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 ntuples and the implicit domain is omitted. That is, we don't have to write complement_{n}, but it needs to be understood in many contexts. (And empty is included in the domain and the range.)
Considers functions on ntuples of natural numbers. That is how the ntuple notation comes into play. Treats sets of ntuples as domains, then functions on these domains to integers. So functions are defined on domains of ntuples, 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 nary function one that produces 0 if the argument ntuple is a member of some set S, and 1 otherwise. This function is also called C_{S} 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.
20000816: 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.
20000816: 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 senseform is then all we have. However, there could be many interpretations of these forms in statements that do not resemble the senseforms, 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.
20000816: 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 senseforms holds. In the example of P(x,y) being the predicate for the statement x = y + 3, it would seem to be so.

created 2001090717:19 0700 (pdt) by
orcmid
