CSC 244/444, 2023 Homework Assignment 1, Sep 12/23 DUE: Tue Sep 19, 9:39 am PLEASE NOTE: This assignment is to be done independently by each student. Do not use LLMs or other AI aids for any part of this assignment. (Later assignments may involve use of ChatGPT or another LLM. At that point, please consult with the TAs or LS if you have no current access to an LLM.) LS and the TAs trust you to comply with the academic honesty guidelines. ALSO: Be brief and to the point -- verbosity is a negative! Marks are indicated parenthetically for each part. The total is 108. ALSO: PLEASE PROVIDE ANSWERS IN PRINT (NOT A SCAN OF HANDWRITTEN NOTES), UNLESS SOME VERY UNUSUAL CIRCUMSTANCES PREVENT YOUR DOING SO. YOU COULD COPY THIS ASSIGNMENTS (USE TXT AND UNICODE FONT) AND INSERT ANSWERS RIGHT AFTER EACH QUESTION -- PLEASE BE HELPFUL TO THE GRADERS! OR, IF YOU LIKE, YOU COULD USE LATEX OR WORD, ETC. 1. a. (3) In one sentence, what is "intelligence", acc. to Steven Pinker? b. (4) How does the "wildebeest tracking" example illustrate this characterization? c. (3) What does Pinker mean by "the cognitive niche"? 2. (8) Give a specific example of each of two kinds of reasoning enabled by "logical" representations of knowledge, other than deduction (avoid examples from the lectures/notes/books). 3. a. (3) Mention three tasks requiring intelligence (in the ordinary, intuitive sense of "intelligence"), as different from each other as you can manage, that AI systems currently do well. b. (3) Mention three tasks requiring intelligence (in the ordinary, intuitive sense of "intelligence"), as different from each other as you can manage, that AI systems currently don't do well. c. (2) What, if anything, do the three tasks in (b) have in common? 4. (8) Which of the following expressions can be WELL-FORMED FORMULAS (wffs), and which cannot, according to the FOL syntax discussed in class (and notes)? Briefly explain what the problem is, or why there is no problem, for each (putative) formula. Remember that we use capitalization for predicates, capitalization for individual constants (the B&L text also allows lower-case individual constants, but we won't), and lower case for variables and functions. Omission of brackets is considered an error if and only if it creates an ambiguity. Don't assume any precedence ordering among ∨, ∧, and =>, but you can assume that ¬ applies to the smallest (well-formed, bracket-balanced) formula that it precedes. Note that certain complex formulas, like B = f(A) ∨ P(C), are unambiguous despite some omitted brackets -- here we know it must be ((B = f(A)) ∨ P(C))), because (f(A) ∨ P(C)) would be ill-formed, combining a term with a formula. For quantified sentences, assume that for delimiting the scope of a quantifier we allow both bracketing (e.g., wffs of form (∀x φ) and the "dot" notation (e.g., sentences of form ∀x.φ, WHERE THE SCOPE OF THE QUANTIFIER IS UNDERSTOOD TO REACH AS FAR TO THE RIGHT AS POSSIBLE WITHOUT INCLUDING AN UNBALANCED RIGHT BRACKET). Note that the syntax we're using allows formulas with unbound variables (i.e., "open" formulas), and it allows the same variable to be used with multiple quantifiers. a. ∀x. Believe(Mary,x) => Believe(John,x) b. Smart(Mary) ∧ Believe(John,Smart(Mary)) c. ∀x. Loves(x,(∀y Child-of(x,y))) d. P(A) => True(P(A)) e. True(p(A)) ∨ True(negation(p(A))) f. P(A) => ∃x P(A,x) g. ∀ x. ∃y. P(x,y,z) h. ∀ x. ∃x. P(x) 5. (5) In one sentence, what is meant by the "aboutness" of language (and similarly logical representations)? 6. Differences between DL (deep learning, neural-net) based and KR&R-based approaches to AI: a. (3) How do the data requirements differ for these approaches? b. (3) How do ways of making inferences differ for these approaches? c. (2) What might we expect about ultimate limitations of DL-based approaches? d. (2) What might we expect about ultimate limitations of KR&R-based approaches? 7. (10) Several real-world examples (and an example from Little Red Riding Hood) were used in class to illustrate the need for knowledge in language understanding. Give your own "real-world" example (one or two sentences), differing as much as possible from the examples so far in CSC 244/444, mentioning a few pieces of knowledge needed to recognize the example as coherent. 8. (6) The KA bottleneck -- estimate how many general facts you know on average about each of the things and ideas that your vocabulary (of around 30,000 words) refers to. Briefly explain your estimation method. 9. (8) What are some ambiguities (at the word level, and in terms of the kinds of phrases making up the sentence) and indexical features in the sentence, "I'm telling you, time flies like an arrow" (Partial hint: Compare with "Fruit flies like a banana", "Avoid snacks like a candy bar") 10. Express in English, as concisely, naturally, and colloquially as you can: a. (2) Long(Eternity) ∧ Time(Eternity) b. (2) Infinite(size-of(Cosmos)) c. (2) True(M-Theory) => (∃x Selectron(x)) d. (4) True(M-Theory) => (∀x ((Boson(x) ∨ Fermion(x)) => (∃y Superpartner-of(y,x)))) 11. Express in FOL, closely matching your choice of predicate and other symbols to the English words (as in the examples in (10)): a. (3) "Alice works at Google or IBM" b. (3) "Some AI-programs play Go" c. (3) "All AI-programs are flawed" d. (4) "No AI-program programs itself" e. (6) "Two partial ToE's exist" ["ToE" = "Theory of Everything"] (Hint: use multiple assertions; BTW, a certain slight flaw is unavoidable) f. (6) "2 is the only even prime"