Foundations of Computer Science
Fall 2007

For today you should have:

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

2) Finished your parzzer.

3) Installed gprolog and started on Harry Potter genealogy.


For next time, you should:

1) Read from Sipser and answer the questions below.

2) Finish the Harry Potter genealogy.

3) Prepare for a quiz.


Prolog
------

Three kinds of statements: facts, rules and questions.

1) facts

parents(lily_evans, james_potter, harry_potter).

The name of the predicate begins with a lower-case letter.

Names of atoms begin with lower-case letters.

Variables begin with upper case letters.


2) questions

A question with no variables returns 'yes' or 'no'.

| ?- parents(lily_evans, james_potter, harry_potter).

yes

A question with variables tries to instantiate the variables
and returns 'yes' or 'no'

| ?- parents(X, james_potter, harry_potter).         

X = lily_evans ? 

yes
| ?- parents(X, Y, harry_potter).           

X = lily_evans
Y = james_potter ? 

yes

There might be more than one instantiation that answers a question.


3) rules

son(X,Y) :- male(X), (mother(Y,X) ; father(Y,X)). 

X is the son of Y if X is male AND 
(Y is the mother of X OR Y is the father of X)

The anonymous variable _ means "anybody"

mother(X,Y) :- parents(X,_,Y).

X is the mother of Y if "X and anybody" are the parents of Y.

Note: in a parents predicate, the order is always 
mother, father, child.

In general the interpretation of a predicate is
an extra-programmatical convention.


Harry
-----

From the previous notes, you should have a version of
harry.pl that has working rules for grandparent and ancestor.

1) If your version of ancestor looks like this:

ancestor(A,D) :- parent(A,D).
ancestor(A,D) :- parent(A,P), ancestor(P,D).

It probably works fine, but if you wrote this:

ancestor(A,D) :- parent(A,D).
ancestor(A,D) :- ancestor(A,P), parent(P,D).

It works for true and crashes for false.

Which is the first indication that prolog is not completely magic.

What's wrong with the second version?


2) Write and test the following rules:

full_siblings(X,Y)  if X and Y have the same pair of parents

siblings(X,Y)  if X and Y have a parent in common


In the next few steps we will figure out a way to represent
facts and rules that will establish the relationship between
Harry Potter and Voldemort.


3) Figure out a way to add facts to the database so that
   ancestor(X,Y) works correctly even if one of the intervening
   ancestors is "Many generations".

   The following should be true:

   ancestor(ignotus_peverell, harry_potter).
   ancestor(cadmus_peverell, tom_marvolo_riddle).

   But make sure ancestor doesn't crash when you test 
   something false!


4) Write and test a rule that checks whether two people are
   first cousins.

   The following should be true:
   
   cousins(harry_potter, dudley_dursley).
   cousins(harry_potter, dudley_dursley).

   You will have to think about the best way to represent
   the fact that Lily and Petunia Evans are sisters.


5) Write and test a rule that checks whether
   two people are related by blood.

   The following should be true:

   related(harry_potter, tom_marvolo_riddle).
   related(harry_potter, cadmus_peverell).

   But the following is false (as far as the database knows):

   related(harry_potter, ginevra_weasley).   



Reading questions
-----------------

Sipser, pages 148-

[You can skim Section 3.2]

1) What do the TM variants in Section 3.2 have in common?




2) What does the Church-Turing thesis state?  Has it been proved?




[You can skim "Terminology for describing Turing machines"]




[Read through the problems on pages 160-162.  Give them some
thought and answer the ones you can.]