CSC 550/650: Assignment 1

Turing Test & Predicate Calculus

  1. Consider the male/female imitation game described by Alan Turing. Suppose you are to play the role of the interrogator, attempting to distinguish between the female and the male pretending to be a female. What line of questioning would you pursue? Explain your reasoning.

  2. Now consider the human/computer imitation game, better known as the "Turing test". What line of questioning would you pursue in order to distinguish between the human and the computer pretending to be human? Explain your reasoning.

  3. For each of the following statements, define a sentence in the predicate calculus that corresponds to it. You may use only the predicates likes(X,Y) (meaning that person X likes Y), happy(X) (meaning that person X is happy), and rich(X) (meaning that person X is rich).

  4. Consider the following sentence from the predicate calculus.

  5. The following story is from Niklaus Wirth's (1976) Algorithms + data structures = programs.
    I married a widow (let's call her w) who has a grown-up daughter (call her d). My father (f), who visited us quite often, fell in love with my step-daughter and married her. Hence, my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (s1), who became the brother-in-law of my father, as well as my uncle. The wife of my father, my step-daughter, also had a son (s2).
    Using the predicate calculus, create a set of expressions that represent the situtation in the above story. Add expressions defining basic family relationships such as the definition of step-daughter, brother-in-law, etc.

  6. Encode the statements you wrote for question 5 as facts and rules in a Prolog program. Use the Prolog interpreter to determine all pairs of grandfather/grandchild. One of these pairs should demonstrate that "I am my own grandfather". Print out a listing of your program, and report all of the grandfather/grandchild pairs on that listing.


  1. Use Modus Ponens and Universal Instantiation on the expressions you wrote for question 5 to prove the conclusion that "I am my own grandfather".