Foundations of Computer Science
Fall 2007

For today you should have:

1) Read from Sipser and answered the questions in notes15.

2) Finished the Prolog list exercises, with the optional
   set intersection and union.

3) Chosen an additional Prolog project and started work.



For next time, you should:

1) Read from Casti and answer the questions below.

2) Finish your Prolog project.

3) Prepare for a quiz.



Prolog list solutions
---------------------

See notes15 for part one.

1) Basic subset works as a boolean, and it works backward, but
   it overflows if run forward.

2) subset works as a boolean, forward and backward, but it requires
   the elements of the set to be unique (which is reasonable).
   Run backward, it generates all permutations of all subsets
   (which is necessary in order to work as a boolean).

3) power is really another implementation of subset, but this
   version requires the elements of the sets to be in order.

4) power_set is a fairly natural recursive definition of a power
   set.  It works forward.  Does it work as a boolean?  Does
   it work backward?


% basic_subset(X,Y) if X is a subset of Y
basic_subset([F|R], Y) :- member(F, Y), basic_subset(R, Y).
basic_subset([], _).

% subset(X,Y) (only works if members of X are unique)
subset([],_).
subset([F|R],A) :- member(F,A), takeout(F,A,X), subset(R,X).


% "power" enumerates the subsets of X; it avoids permutations
% by requiring the elements to be in order (so the elements have
% to be integers)
% This is from http://kti.mff.cuni.cz/~bartak/prolog/sets.html

power([H1|T1],[H2|T2]) :- lt(H1,H2), power(T1,[H2|T2]).
power([H|T1],[H|T2]) :- power(T1,T2).
power(_,[]).

% lt is true if either argument is a variable; otherwise it uses <
lt(X,Y) :- var(X); var(Y).
lt(X,Y) :- nonvar(X), nonvar(Y), X<Y.

% powerset(A,B) is true if B is the power set of A
powerset([], [[]]).
powerset([F|R], X) :- powerset(R,Y), addeach(F,Y,Z), append(Y,Z,X).

% addeach(X, Y, Z) if Z is the result of adding X to each list in Y
addeach(_, [], []).
addeach(X, [A|R1], [B|R2]) :- addeach(X, R1, R2), putin(X, A, B).


Incompleteness
--------------

What you should read:

Casti, Five Golden Rules, Chapter 4

pages 152 (starting with "Form and Content")
   to 174 (ending at "Tough times")

1) What was the ultimate philosophical goal of the challenge
   Hilbert posed?


2) Was is a formal system?  What is "the theorem" of a formal
   system?


3) What is a metamathematical property?


4) What does the "dictionary" in Figure 4.4 do?


5) What does it mean to say that a formal system is complete?


6) The first complete sentence on the top of page 158, beginning
   "And you certainly can't," is nonsense.  Why?


7) What is the Big Idea #1 that underlies Godel's proof?


8) What is Big Idea #2?


The statement of Godel's Theorem on page 163 is called the
First Incompleteness theorem.


The Second Incompleteness Theorem takes on the second part
of Hilbert's challenge, provable consistency.


9) What is the Turing Test?


10) What is the basic claim Penrose makes about the limitations
    of machines?


11) Casti outlines three responses to Penrose and Lucas.  What
    are they?


12) What is the smallest dull number?


13) What is the definition of omega?


14) How do we know that we can't compute omega?


15) What does the word 'cabalistic' mean?