LMU ☀️ CMSI 3801
THEORIES OF COMPUTER AND HUMAN LANGUAGES
Quiz 1 Answers
  1. Automation is computation with little to no ________________.
    Human intervention
  2. Show how to represent the following graph as a string of symbols. (You have some flexibility in the notation you choose, but your representation should be clear and unambiguous, that is, the graph must be reconstructible perfectly from your string.)

    smallstategraph.png

    AB/BC/CA/CD/DD/DE/EC/CE (many other answers possible)
  3. What are the three views of language we’ll be exploring in this course?
    • Engineering, statistics, math
    • anthropology, cognitive science, engineering
    • Formal languages, human languages, LLMs
    • Formal languages, neural networks, LLMs
    • Cultural languages, formal languages, human languages
  4. Who wrote Al-Jabr?
    • Thābit ibn Qurra
    • Al-Kindi
    • Andrew Forney
    • Al-Khwārizmī
    • Al-Abbās ibn Saīd al-Jawharī
  5. Which of the following are true about the Analytical Engine?
    • Ada Lovelace wrote a Fibonacci number program for it.
    • Isaac Newton consulted with Babbage during its development.
    • It could perform general-purpose computation.
    • Luigi Manabrea built a working implementation.
  6. Match each of the following terms with their correct descriptions (by drawing lines connecting the left side terms to the right side definitions).
    7.   Soundness     ====>  All truths are provable
  Completeness  ====>  All provable statements are true
  Consistency   ====>  You cannot prove a contradiction
  Decidability  ====>  An algorithm exists to determine provability
  7. Gödel’s incompleteness theorems are widely misunderstood, especially his first one. Which of the following is the most accurate description of what the theorem said?
    • Every true mathematical statement can be proven.
    • There are true mathematical statements that cannot be proven.
    • There is a hole at the bottom of mathematics.
    • No formalization of mathematics can capture all mathematical truths.
    • A consistent axiomatic system containing arithmetic cannot prove all truths.
  8. Which of the following did Turing accomplish with his 1936 paper?
    • He described a machine whose operation coincided with what is likely our intuitive notion of computation.
    • He showed there are problems that cannot be solved by any algorithm.
    • He demonstrated an algorithm for Entscheidungsproblem.
    • He demonstrated computational universality.
    • He showed that Church and Gödel's notions of computability were flawed.