The Miser Project

Miser Project Readings
Computation Theory Definitions, Nomenclature,
and Elementary Concepts


0.01 2017-08-29 16:40

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

0.1 Definitions

0.2 Mathematical Notions and Terminology

0.3 Definitions, Theorems, and Proofs

0.4 Types of Proof

Exercises and Problems


0.1 Definitions

Algorithm or Effective Computational Procedure
mechanical procedures by which the answers to any one of a class of questions can be obtained. [Davis1982]
Automata Theory
definitions and properties of mathematical models of computation.  Theories of computability and complexity require a precise definition of a computer.  Automata theory provides formal definitions of computation.  [Sipser1997]
Complexity Theory
study and theory about what makes some problems computationally hard and others easy [Sipser1997].  
Computability Theory
classification of problems by those that are solvable by computation and those that are not.  Computability theory introduces several of the concepts used in complexity theory [Sipser1997] .

Nomenclature and Definitions [Davis1982: Introduction, 1], for reconciliation with Sipser.  Incorporation in a broader glossary eventually.

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


0.2 Mathematical Notions and Terminology

Notations [Introduction, 3] - From [Davis1982]

3.1 Tuples

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.

3.2 Sets

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 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 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.)

3.3 Functions

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(RC(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.

3.4 Statements (propositions)

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.

3.5 Predicates

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.

3.6 Quantifiers

0.3 Definitions, Theorems, and Proofs

0.4 Types of Proof

Exercises and Problems

Exercise 0.1



Davis, Martin. Computability and Unsolvability. Dover (New York: 1958, 1973, 1982). ISBN 0-486-61471-9 pbk.
Sipser, Michael Introduction to the Theory of Computation.  PWS Publishing (Boston, MA: 1997).  ISBN 0-534-94728-X.


0.01 2014-05-03-09:49 Repaved Version
The page is updated to conform to current styles and formats.  The material is preserved as a historical matter and to avoid breaking any links that may have existed to it.
0.00 2001-09-07-17:19 Develop Initial Notes (orcmid)
Extract notes on how this material is applicable to the Miser Project
Construction Structure (Hard Hat Area)

You are navigating the Miser Project.

created 2001-09-07-17:19 -0700 (pdt) by orcmid
$$Date: 17-08-29 16:40 $
$$Revision: 17 $