```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
```