November 10

* Chomsky Hierarchy

  Chomsky numbered the four families of languages that make up the
  Chomsky hierarchy.

  Type 0 Recursively enumerable TM  Phase-structured grammars
  Type 1 Context Sensitive      LBA CSG
  Type 2 Context Free           PDA CFG
  Type 3 Regular                FSM RE

  Restrictions on the grammars increase with the type number.


* Decidability

   A "decision problem" consists of a set of questions whose answers
   are either yes or no.

   A solution to a decision problem is a procedure that determines the
   yes/no answer for each question in the set.

   A decision problem is "undecidable" if there is no algorithm that
   solves the problem.

   The ability of Turing machines to return affirmative and negative responses
   makes them appropriate for constructing solutions to decision problems.

   The "Church-Turing thesis" asserts that a Turing machine can be designed to
   solve any decision problem that is solvable.

   To establish that a problem is unsolvable it thus suffices to show that there
   is no Turing machine solution.

   We are not yet looking at efficiency.


   Example

      The question "Is 8 a perfect square?" is an example of the type of
      question under consideration in a decision problem.

      A decision problem usually consists of an infinite number of
      related questions.

      Decision Problem:  Determine whether an arbitrary natural number is a
      perfect square.

	 Is 0 a perfect square?
	 Is 1 a perfect square?
	 Is 2 a perfect square?
	 ...

      Every search problem (search for a solution) has a corresponding
      decision (yes/no answer) problem.

      Search Problem:  Input = G, a context-free grammar

	 Desired Output = shortest w such that w has two leftmost derivations
	    (if G is ambiguous) or "not ambiguous" if G is unambiguous.

      Corresponding Decision Problem:  Input = G, a context-free grammar

	 Desired Output = "yes" if G is ambiguous
			  "no"  if G is not ambiguous


      Formally, a decision problem is a set.
      In this case, Assume  is the encoding in {0,1}* for grammar G, where we
      employ some reasonable encoding conventions.  Then the decision problem
      above can be stated:

	 L_ambiguous = {:  G is a CFG that is ambiguous}

      If L_ambiguous is recursive, then we say the problem of determining
      whether a CFG is ambiguous is "decidable".

      If L_ambiguous ia not recursive, then the problem is "undecidable".



   In general, we have taken a search problem and perhaps made it easier
   by replacing it with a decision problem.  If the decision problem is
   undecidable, then certainly no algorithm exists for the search problem.


   Example

      - Does there exist a substring of exactly 83 adjacent 7s in the decimal
	expansion of pi?

	This is decidable!!!  There exists an algorithm to solve it.
	The algorithm is either M_yes or M_no, where M_yes says "yes",
	M_no says "no", regardless of input.  We just don't know which
	algorithm is the correct algorithm, but we know the right one exists.

   Example

      - A more general problem is

	Does there exists a substring of exactly n consecutive 7s in the
	decimal expansion of pi?

        Language is {n:  there exists substring of exactly n ... in pi}.
	This may or not be recursive (decidable).

   Example

      - L = {n:  there exists substring of >=n consecutive 7s in the decimal
	expansion of pi}.

	This is recursive.
	In fact, it is regular!

   Optional

      Read book to see an example of a language that is not recursively
      enumerable.

      No machine can halt on acceptance of a string in this language.


* Logic

  Instead of using languages to understand the theory of computation, we
  will now use languages to generate statements that have a true or false
  value.

  The "meaning" of a sentence (logically) is a mapping onto the "real world".
  This mapping is an "interpretation" (interpretation of C code, for example).

  A sentence is "valid" (necessarily true, tautology)
  iff it is true under all possible interpretations.

     A or not-A

     Interpretation of A could be:
	- Today is Monday
	- 2 + 3 = 5

     The above statement is valid.  These statements are not valid.
                A & not-A
                A v B

      The last statement is "satisfiable", meaning there exists at least one
      interpretation that makes the statement true.  The previous statement is
      "unsatisfiable".

   - An "interpretation I" consists of
        An assignment of truth values to all proposition symbols I(S)

   - Models: worlds in which a particular sentence is true
        under at least one interpretation

* Logics

      - Propositional logic
        Symbols represent entire facts
        Boolean connectives (&, v, ->, <=>, ~)
        Propositions (symbols, facts) are either TRUE or FALSE

      - First-order logic
        Extend propositional logic to include
           variables, quantifiers, functions, objects


*  Propositional Logic

   - Symbols represent entire facts
     Formulas in propositional calculus (the language of propositional logic)
     using symbols.

	P, Q, etc.

     An formula is an "atomic formula" if it follows one of these rules.

	1.  A single symbol with a T/F value is an atomic formula.
	2.  If f,g are atomic formulas, then f v g is an atomic formula
	    (the disjunction of f and g).
	2.  If f,g are atomic formulas, then f & g is an atomic formula
	    (the conjunction of f and g).
	2.  If f is an atomic formulas, then -f is an atomic formula
	    (the negation of f).

   - A "truth assignment" is a function from a set of atomic formulas to the
     set {T, F} of "truth values".

     Let alpha be a truth assignment.  The function alpha is defined as

     1.  alpha(f v g) = T if alpha(f) = T or alpha(g) = T
			F otherwise
     2.  alpha(f & g) = T if alpha(f) = T and alpha(g) = T
			F otherwise
     3.  alpha(-f)    = T if alpha(f) = F
			F otherwise

   - The true/false value of propositions and combinations of propositions
     can be calculated using a truth table

     The first n columns are labeled with the atomic subformulas of f,
     subsequenct columns are labeled with the other subformulas of f that are
     constructed from the atomic formulas.
     The last column is labeled with f itself.

     The table has 2^n rows, one for each n-tuple of truth-values for
     the atomic formulas.

     The tables is filled with T and F as appropriate.

     The formula is valid when the rightmost column consists entirely of Ts.

     The formula is satisfiable when the rightmost column contains at least
     one T.

     The formula is unsatisfiable when the rightmost column contains all Fs.

     A row in the truth table is one interpretation of the symbols.

   Examples


   A B | A v B         A | -A       A B | A & B
   ----+------         --+---       ----+------
   T T |   T           T | F        T T |   T
   T F |   T           F | T        T F |   F
   F T |   T                        F T |   F
   F F |   F                        F F |   F


   A B | A->B          A B | A<->B
   ----+-----          ----+------
   T T |  T            T T |   T
   T F |  F            T F |   F
   F T |  T            F T |   F
   F F |  T            F F |   T