Appendix

Table of Contents

A. From Symbolic Software 1.0 to Stochastic Software 2.0

$\hookleftarrow$ Table of Contents

In which we historically retrace the development and failure of the discretely symbolic approach to build artificially intelligent machines with common sense and motivate the need to transition from logical and finitely discrete software 1.0 to stochastic and infintely continuous software 2.0.

A.1 From Psychology to Artificial Intelligence

The transition between the two representations happened relatively recently at a summer worshop at Dartmouth in 1956. There, a group of researchers unsatisfied with the theories that the discipline of psychology were using to explain the phenomena of the mind and it’s intelligence came together to discuss a different approach, namely, one where the computer is the instrument for conducting scientific experiment. Although seemingly trivial from the modern perspective where most if not all sciences use the computer, they were were arguably the first with motivation arisen from the epistemological: using the computer as basis for the science of mind (and all sciences in general) strengthened it’s explanations from the observationally simple like stimulus-response to the constructively complex such as neural networksPractical applications are often a result of inquiry that is philosophical and gradiose with no immediately obvious economic value. Namely, computers with Hilbert wanting to automate mathematics as beers, tables and mugs; language models with McCarthy, Minsky, Newell and Simon wanting to mechanize and naturalize the mind.. That is, constructive because explaining via computer means simulating the phenomena by programming processes with procedures. And, complex because computers allow for the simulating of many things at onceParaphrasing Minsky, “Under certain conditions mathematical analysis can describe complex phenomena where the parts of the system can be treated as individual and independently random (i.e statistical thermodynamics), but there is no reason to suspect that intelligence is the result of averaging out many events.”. The proposal for the workshop states:

We propose that a (…) study of artificial intelligence be carried out (…) the study is to proceed on the basis of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it.

Besides the intellectual pursuit of finding better explanations for a clearer picture of reality, using the computer also means something quite practically profound. If the explanation it comes up with are accurate, we will have artificial systems that exhibit behavior which we would attribute intelligence to. This is what the Turing Test posited and predicted in 195X (todo, read computing machinery and intelligence). artificial intelligenceartificial intelligence natural language processingnatural language processing computational linguisticscomputational linguistics. And this is why we have ChatGPT.

In this book we embark on a quest to build from scratch our own deep neural network like ChatGPT by implementing nanochat and our own deep learning framework like PyTorch by implementing teenygrad capable of running nanochat itself. These systems by nature are stochastic and infintelyTurns out not quite infinte, as we will see in chapter 3. continuous software 2.0 rather than the logical and finitely discrete software 1.0 and are implemented not by programming algorithms and their procedures line by line with sets, maps, lists, trees, and graphs, but rather, by searching the space of programs by providing a goal to calculus, which then optimizes said goal — in the case of ChatGPT, producing a probability distribution over tokens — with the linear algebra of tensors. However, there was a time where the dominant approach involved using software 1.0 and in chapter 0 we will build various systems using such techniques to display their shortcomings, understanding the underlying philosophical principle, and ultimately motivating the need for software 2.0The art of programming software 1.0 is necessary however on your quest to learn software 2.0! PyTorch is embedded and implemented within Python afterall. For instance, to those who spent countless nights learning esotoric spells such as that of dynamic programming to enter the kingdoms of our feudal lords only to create web page buttons should not fret as it turns out that dynamic programming over a graph is in fact the beating heart of all deep learning frameworks.

If you’d like to revisit the fundamentals of programming, we recommend the Data Centric Introduction to Computing, which begins with the teaching language Pyret and graduates to Python. You can then take a look at the documentation of the Python Tutorial, Python Language Reference and Python Standard Library.

briefly mention intelligence must be told knowledge before learning it and such knowledge should be represented a symbolic logic

• mccarthy’s excerpts from “programs with common sense”
• minsky’s “descriptive languages and problem solving”
• newell and simon’s symbolic hypothesis
• newell knowledge level

Are you ready to begin?

A.2 Weizenbaum Cheats Turing’s Test with the Pattern Matching of ELIZA

Humans, it seems, know things: and what they know helps them do things. The early approach to artificial intelligence using logical and finitely discrete techniques from software 1.0 focused on building systems that reasoningreasoned over an internal representationrepresentation of knowledge. Iteratively deepening software 1.0’s symbolic perspective of such terms will be the focus of this first chapterBy the end of the book you will have come to understand the software 2.0 perspective of such terms..

Although there was various flavors of the symbolic approach to AI — game playing, puzzle solving, problem solving to name a few — our focus is on building conversational machines within the realm of natural language processing and computational linguistics, to pass something like the aforementioned Turing Test. With that said, what is the simplest way to build a conversational machine with the logical and finitely discrete techniques from software 1.0?

Warning

Pause and think!

What if we represented words with strs and, produce answers as output with if statements conditioned on questions as input?

That’s effectively what the ELIZASee A Computer Program For the Study of Natural Language Communication Between Man and Machine (Weizenbaum 1966) system doesDo you feel dissapointed after learning ELIZA’s trick? The trick with all explanations is that after the explanation, no trick remains. See Matter, Mind, and Models (Minsky 1965), and The Nature of Explanation (Craik 1952). You might feel the same way by the end of the book even after learning how nanochat and teenygrad work under the hood. Don’t say we didn’t warn you! to imitate a Rogerian psychotherapist.

For instance, a question that tends to get asked is the meaning of life. Answering such question seems quite grandiose for now, so let’s have our system produce some random string for now. Let’s document and interatively test our exampleThe implementation of all functions implemented in the book will start with examples, following the principled design of programs with the How to Design Programs’ Design Recipe. We still find it useful in the era of agentic coding. with Python’s convinent standard library module docttest:

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'
  """
  if input == "What's the meaning of life?": return "42"
  else: raise NotImplementedError("")

  if __name__ == "__main__":
    import doctest
    doctest.testmod()

Let’s start with other questions that are perhaps less grandiose but as equally important in which a patient might ask a psychotherapist. For instance, a patient reporting to a therapist that they are unhappy or upset. Given that ELIZA imitates a Rogerian psychotherapist which follows the principle of person-centered therapy — that is, no immediate rejection (todo: read wiki) — we might expect on an a priori basisWe can also empirically confirm the following question-answer pairs by consulting the appendix in (Weizenbaum 1963). that our system responds like so:

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'
  """
  if input == "What's the meaning of life?": return "42"
  else:                                       raise NotImplementedError("")

if __name__ == "__main__":
  import doctest
  doctest.testmod()

Evaluating the tests fails as expected. How should we implement the function body for eliza() so that they pass?

Warning

Pause and think!

The most naive way to make them pass is to add an if-then rule for each example, following the question-answer pair for the meaning of life:

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'
  """
  if input == "What's the meaning of life?": return "42"
  elif input == "I am unhappy":              return "Why do you say you are unhappy?"
  else:                                       raise NotImplementedError("")

if __name__ == "__main__":
  import doctest
  doctest.testmod()

Clearly eliza lacks any true understanding of word meaning found in natural language, for it’s simply reflecting the prompt back to the user. In the paper:

The ELIZA program itself is merely a translating processor in the technical programming sense. Gorn [2] in a paper on language systems says: ‘Given a language which already possesses semanticssemantic content, then a translating processor, even if it operates only syntaxsyntactically, generates corresponding expressions of another language to which we can attribute as “meanings” (possibly multiple — the translator may not be one to one) the “semantic intents” of the generating source expressions; whether we find the result consistent or useful or both is, of course, another problem.’

The classic linguistics example to distinguish syntactic form and semantic meaning comes from Syntactic Structures (Chomsky 1957):

• Furiously sleep ideas green colorless
• Colorless green ideas sleep furiously

where the first sentence is gramatically incorrect whereas the second, while gramatically correct, is semantically meaningless(todo).. With ELIZA however, it doesn’t outright produce sentences that are as meaningless as the second sentence, but as the interaction with the chatbot progresses, the mirage of such semantic understanding unveils itself, and most people start to understand the gist of ELIZA’s gimmicks.

But even if only operating syntactically speaking, another issue is that the implementation clearly does not scale, for in the case where our patient prompts eliza with cases not handled — that they are upset for instance — our implementation immediately fails:

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'

  >>> eliza("I am upset")
  'Why do you say you are upset?' # <-- FAIL

  >>> eliza("Why does Alice hate me?")
  'Why do you say Alice hates you?' # <-- FAIL
  """
  if input == "What's the meaning of life?": return "42"
  elif input == "I am unhappy":              return "Why do you say you are unhappy?"
  else:                                       raise NotImplementedError("")

if __name__ == "__main__":
  import doctest
  doctest.testmod()

We can add another conditional statement to handle such case, but then the the patient can come in reporting yet another sentiment after that. Although enumerating through the entire space of possible questions a patient could ask is indeed intractable, perhaps we could collapse said space with a few conditional statements that provided reuse within each branch. For instance, in the case where a patient’s prompt takes the syntactical form “I am BLAH”, eliza can respond with “Why do you say you are BLAH?” independent of BLAH’s semantic meaning. In another case with “BLAH hates me”, eliza can respond with “Why do you say BLAH hates you?”.

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'

  >>> eliza("I am upset")
  'Why do you say you are upset?' # <-- FAIL

  >>> eliza("Why does Alice hate me?")
  'Why do you say Alice hates you?' # <-- FAIL
  """
  if input == "What's the meaning of life?": return "42"
  elif input == "I am BLAH":                 return "Why do you say you are BLAH?"
  elif input == "BLAH hates me":             return "Why do you say BLAH hates me?"
  else:                                       raise NotImplementedError("")

if __name__ == "__main__":
  import doctest
  doctest.testmod()

In order to implement the code sketch above, some formal language theory is needed. The theory models languagelanguage as a set of strings, where each string is a sequence of elements from some finite alphabetalphabet. Even if such set is infinite, the set itself can be characterized with a finite set of rules. The core interest of such theory are the syntactical aspects of languages, namely the membership problemmembership problem. That is, to determine based off structural form whether a given string is in a language or not. Given that ELIZA is merely operating with the syntactic structure of the “Rogerian psychotherapist language”, that is not a problem.

In our case, we’d like to somehow define the language of all strings that take the form “I am BLAH”, and then match all strings that are inside that set. How do we characterize such a set? We can do so with a regular expressionregular expression, which defines the regular languageregular language of said strings, “I am BLAH”. A regular expression is one which can include the following elements

• a literal character drawn from some alphabet $\Sigma$
• the empty string $ϵ$
• the Kleene star $R^{\ast }$, where $R$ is a regular expression
• concatenation $RS$, where $R$ and $S$ are regular expressions
• alternation $R|S$, where $R$ and $S$ are regular expressions
• and parentheses $(R)$, where $R$ is a regular expression

With Python particularly, regular expressions are available via standard library’s re module with a two step process.

1. The first step is passing a regular expression to re.compile() to produce a re.Pattern object.
2. Then, the second step is to match against said pattern with an input string via Pattern.search(string), Pattern.match(string) or Pattern.fullmatch(string) which returns a corresponding re.Match object or None.

However if the pattern is only going to be matched against a single time without any reuse, you can evaluate the re.Pattern and re.Match objects with a single function invocation rather than two. For example:

import re
pattern = re.compile(r"I am unhappy")
result1 = pattern.fullmatch(r"I am unhappy")    # match
result2 = pattern.fullmatch(r"foobar")          # no match
result3 = pattern.fullmatch(r"You are unhappy") # close, but still no match
print(f'{result1=}')
print(f'{result2=}')
print(f'{result3=}')

result1_singlestep = re.fullmatch(r"I am unhappy", "I am unhappy") # match, with a single call

In our case where we’d like to characterize all strings that take the form “I am BLAH”, we need to use the Kleene star which effectively acts as a wildcard, and subsequently capture the BLAH with Math.groups()

import re
result = re.fullmatch("I am (.*)", input)
print("captured: {0}?".format(*result.groups()))

Using our new machinery with regular expression in eliza()’s implementation, we now have:

import re

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'

  >>> eliza("I am upset")
  'Why do you say you are upset?'
  
  >>> eliza("Why does Alice hate me?")
  'Why do you say Alice hates you?'
  """
  if match := re.fullmatch("What's the meaning of life?", input): return "42"
  elif match := re.fullmatch("I am (.*)", input):                 return "Why do you say you are {0}?".format(*m.groups())
  elif match := re.fullmatch("(.*) hate (.*)", input):            return "Why do you think {0} hates {1}?".format(*m.groups())
  else:                                                           raise NotImplementedError("")

print(eliza("I am very unhappy these days")) # Why do you say you are unhappy?

Tests pass! Let’s add some more rules, including a catchall rule in the else branch where any phrase uttered in which eliza() does not recognize will be responded with "Please go on.". It’s effectively an escape hatch for eliza()’s utter lack of semantic understanding with word meaning.

todo you -> me me -> you

import re

def eliza(input: str) -> str:
  """
  >>> eliza("What's the meaning of life?")
  '42'

  >>> eliza("I am unhappy")
  'Why do you say you are unhappy?'

  >>> eliza("I am upset")
  'Why do you say you are upset?'
  """
  if match := re.fullmatch("What's the meaning of life?", input): return "42"
  elif match := re.fullmatch("I am (.*)", input):                 return "Why do you say you are {0}?".format(*m.groups())
  elif match := re.fullmatch("It seems that (.*)", input):        return "What makes you think {0}?".format(*m.groups())
  elif match := re.fullmatch("(.*) hate (.*)", input):            return "Why do you think {0} hates {1}?".format(*m.groups())
  else:                                                           return "Please go on." # <-- the magic trick

print(eliza("I am very unhappy these days")) # Why do you say you are unhappy?
print(eliza("I am very unhappy these days")) # How long have you been very unhappy these days?
print(eliza("It seems that you hate me"))    # What makes you think you hate me?

With the last transformation rule, you can see how brittle ELIZA’s so-called “understanding”, or semantics, truly is. The primary reason a simple pattern matcher over strings can be endowed with human understanding (in other words, why the magic works) is because of the psychiatric context — especially the Rogerian one with person-centered therapy — where users are effectively talking with oneselvesIn a 1978 interview, “Well, I would deny that that there’s any important sense, non-negligible sense in which the program understands. It certainly creates the illusion of understanding. there’s no question about that. But we have to understand that that illusion is an attribution that the person conversing with the program contributes to the conversation. It’s not a function of the program itself.”. The paper goes on to report that:

This mode of conversation was chosen because the psychiatric interview is one of the few examples of categorized dyadic natural language communication in which one of the participating pair is free to assume the pose of knowing almost nothing of the real world. If, for example, one were to tell a psychiatrist “I went for a long boat ride” and he responded “Tell me about boats”, one would not assume that he knew nothing about boats, but that he had some purpose in so directing the subsequent conversation. It is important to note that this assumption is one made by the speaker. Whether it is realistic or not is an altogether separate question. In any case, it has a crucial psychological utility in that it serves the speaker to maintain his sense of being heard and understood.

Important

Our eliza() will not qualitatively improve it’s breadth of common sense nor it’s depth of understanding by simply adding another if-then rule. This is because it’s trying to describe a reality with too many parts to count.

Describing a reality with too many parts is the philosophical principle and problem that logical and finitely discrete techniques from software 1.0 ultimately run into. But perhaps it’s too soon to jump the software 1.0 ship to the stochastic and infintely continuous methods of software 2.0? Afterall, ELIZA’s representation are only strs, and it performs no reasoning whatsoever. Maybe all we need to build a natural language processing system that can match the capability of nanochat is with a stronger syntactic and semantic analysis?

A.3 Wood’s Winograd Challenge with the Translation of LUNAR

(INSERT LUNAR EXAMPLE)

Computers are being used today to take over many of our jobs. They can perform millions of calculations in a second, handle mountains of data, and perform routine office work much more efficiently and accurately than humans. But when it comes to telling them what to do, they are tyrants. They insist on being spoken to in special computer languages, and act as though they can’t even understand a simple English sentence.

Let us envision a new way of using computers so they can take instructions in a way suited to their jobs. We will talk to them just as we talk to a research asisstant, librarian, or secretary, and they will carry out our commands and provide us with the information we ask for. If our instructions aren’t clear enough, they will ask for more information before they do what we want, and this dialog will all be in English.

Procedures as a Representation for Data in a Computer Program for Understanding Natural Language (Winograd’s Dissertation 1971)

change segue to be more historical (minsky’s semantic informationation processing, the intros to wood and winograd’s dissertations)

Starting where the previous chapter left off, how can we build a natural language processing system with a stronger analysis of syntactic (grammar) and semantic (meaning) of the English language?

Warning

Pause and think! When questions become more difficult to think about from first principles perhaps such as this one, one heuristic is to use a combination of both history and theories from other disciplines as a guide.

That’s effectively what the LUNAR and SHRDLU systemsPresented across a series of papers. See (Woods 1969), (Woods 1970), (Woods 1971), (Woods 1972), and (Winograd 1971), respectively. do. The former, implements a natural language processing system to interface with a database containing chemical analysis data on lunar rock and soil from the from the Apollo 11 moon missions so that non-expert geologists could express their questions in the natural language of English rather than a formal one such as SQL. The latter, implements the same but rather than interface with a database, it does so with a 3D graphically simulated world with blocksCalled Blocks World, a toy environment which was home to many of MIT’s symbolic AI projects.. The LUNAR and SHRDLU systems were amongst the first natural language proecssing systems to implement a deeper level of word understanding via natural language compilers, compared to systems like ELIZA. Like many of the AI systems at the time, although seemingly applied to the narrow domains of toy environments, these researchers were after general principles.

(quote something from woods, winograd, or minsky’s semantic information processing)

A.3.1 From Linguistics to Logic

Although we might not know exactly how that’s done, we might be somewhat familiar with the distinction of “lower level” vs “higher level” languages where the former are closer to the machine (whatever that may mean) such as C++ and the latter are English-like (whatever that may mean) like Python. Whatever is going underneath there, it seems like these languages understand at least something about our intent in order to preserve it through the translation from a higher level language to a lower level one. Perhaps we can use the same techniques that formal programming languages use but extend them one level “higher” by applying them to the natural language of English itself?

With the approach settled, the problem reduces down into answering the question of how do we implement a compiler? Depending on your appetite, you can try to tackle this question from first principles as well. We however don’t have the ability nor time to perform such a feat, and so we will consult the existing literatureWe recommend Programming Languages: Application and Interpretation (Krishmaurthi 2022).

The first idea to understand is that a compiler is a function which takes a string in and produces a string out (programs are written in text editors afterall) where the input string is referred to as the source program and the output string as the target program. While a traditional compiler might take in C as the source language and produce x86 as the target language, LUNAR takes in a question expressed in English and produces a query expressed in SQL. (todo: remove SQL) Just like a human translator, a compiler has a two step process:

1. First, a compiler needs to understand the message expressed in the source language
2. Then, said compiler can translate the message expressed in the target language

A.3.1 Analysis: Understanding the Source

Starting with the first step, that awfully sounds like formal language theory’s membership problem which we encountered in the previous chapter. That is, determining whether a given string is in a language (subsequently modeled as a set of strings) or not. Perhaps we can reuse regular expressions? Why not try the machinery we already have?

Clearly, regular expressions have no problem describing languages

memory to model long range dependencies i.e a^nb^n (push down, recursion (via stack)) a lexical analysislexical analysis are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a lexical grammarlexical grammar are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum

a syntactic analysissyntactic analysis are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a syntactic grammarsyntactic grammar are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a syntax treesyntax tree are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a derivationderivation loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a parserparsing is the problem of finding a derivation for a string in a grammar (recognizer)

a context-free languagecontext-free language are defined by context-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum a context-free grammarcontext-free grammar loremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsumloremipsum

It first converts the source program from a concrete syntaxconcrete str to a more abstract syntaxabstract data structure that has more “understanding” of what’s being spoken to it compared to a simple silly str. Because this abstract representation of the program is not the final representation (namely x86), it’s referred to as the <span

A.3.2 Synthesis: Translating to the Target

While there do exist compilers that perform this translation in a single step, most compilers (and interpreters for that matter) allocate an intermediate representationintermediate representation of the program in order to better analyze, understand, and perhaps optimize said programSaid compilers that translate in a single step are single-pass compilers, primarily from the past when memory bottlenecks prevented the allocation of data structures that represented the entire source program. This is why you can’t invoke a function above it’s definition in C, unless you explicitly provide a forward declaration.. The translation step from source to intermediate representation and from intermediate representation to target are called parsingparsing and generationgeneration respectivelyWith all industrial language implementations, there is almost always a third step in between the two, which optimizes the program.

def compile(source: str) -> str:
  """translates a source program expressed in C to a target program expressed in x86

  """
  ir = parse(source)
  target = generate(ir)
  return target

from dataclasses import dataclass
@dataclass
class IR():
  # ???
def parse(source: str) -> IR: raise NotImplementedError("")
def generate(ir: IR) -> str: raise NotImplementedError("")

def lunar(english_source: str) -> str:
  """translates a source question expressed in english to a target question expressed in SQL
  (todo, examples)
  """
  ir = parse(source)
  target = generate(ir)
  return target

from dataclasses import dataclass
@dataclass
class IR():
  # ???

def parse(source: str) -> IR: raise NotImplementedError("")
def generate(ir: IR) -> str: raise NotImplementedError("")

Evaluating the code above fails as expected. Before implementing the respective function bodies of parse() and generate(), we need to design the IR data structure.

A compiler however is only a program translatortranslator, namely from the C language to the x86 language. In order to produce a final answer you will need a program evaluatorevaluator for x86, which is any Intel processor that understands x86. Similarly with LUNAR, after translating the query from English to SQL, a database that understands SQL is neededWe will learn about the internals of the former evaluator (a hardware processor) in Chapter 3 when accelerating linear algebra in order to implement teenygrad. The later evaluator (a database processor) however is unfortunately out of scope — if you’d like to learn more about database internals, we recommend Andy Pavlo’s CMU 15-445/645.. Following the Design Recipe, let’s start with examples for lunar().

def lunar(english_source: str) -> str:
  """translates a source question expressed in english to a target question expressed in SQL

  """
  ir = parse(source)
  target = generate(ir)
  return target

from dataclasses import dataclass
@dataclass
class IR():
  # ???
def parse(source: str) -> IR: raise NotImplementedError("")
def generate(ir: IR) -> str: raise NotImplementedError("")

carnap, montague, frege (philosophical principles)

(Woods 1972 BBN Report)

Although the goal of accepting an input request in any phrasing which a user might ask is one which will require additional grammar development and semantic work, the system has already achieved considerable progress towards this goal, and the components and organization which we have used in building the system permit conditinoal gradual evolution towards its achievement.

In Progress in Natural Language Understanding — An Application to Lunar Geology (Woods 1973)

The advent of computer networks such as the ARPA net has significantly increased the opportunity for access by a single researcher to a variety of different computer facilities and data bases, thus raising expectations of a day when it will be a common occurrence rather than an exception that a scientist will casually undertake to use a computer facility located 3000 miles away and whose languages, formats, and convetions are unknown to him. In this foreseeable future, learning and remembering the number of different languages and convetions that such a scientist would have to know will require significant effort — much greater than that now required to learn the conventions of his local computing center.

• end the chapter with lighthill
• end chapter with winograd’s two phd students sergey brin and larry page duck semantics with information retrieval and search engine.
• motivate expert systems (feigenbaym)
• the other reaction is lenat with CYC (let’s increase the knowledge base)

Important

Although lunar()’s depth of understanding the natural language of English is deeper than eliza()s, it came at the cost of a shallower breadth in it’s common sense. That is, simply adding more syntactic grammar or semantic interpretation rules will not enable lunar() to start helping patients in the psychiatric setting because it will always be limited to the chemical analysis data in it’s knowledge base from the Apollo 11 moon missions. Although in different ways, LUNAR too, like ELIZA, is trying to describe a reality with too many parts to count.

A.4 Lenat’s Advice Taker with the Frames of CYC

• minsky’s programs with common sense
• mccarthy’s ontology of frames

A.5 From A Logical to Distributional Semantics

feigenbaum’s concept learning lenat’s bitter lesson: from the tractatus to the investigations

lighthill report (1973)

then expert systems in ’80s (feigenbaum and raj reddy), expert systems being abandoned in ’90s, creating the second winter. Parallel Distributed Processing (Rumelhart and McClelland, 1986)

although obvious posthoc that neural networks, this was all predicated with foresight by wittgenstein.

vector semantics by (Osgood et al. 1957) distributional semantics (Harris 1954)

• from feigenbaum/reddy to pdp
• from the organon (knowledge representation and reasoning with upper ontologies and deductive inference) to norvum organon (occam’s razor)
• from the tractatus to the investigations is effectively the transition from software 1.0 to sofware 2.0
• to understand the claude, we must return to claude
• data science begins where computer science begins

question answering systems eventually incorporated the web as it’s knowledge base, and the field of information retrieval emerged. https://start.csail.mit.edu/index.php

A.6 Summary

One quick way to summarize the software 1.0 approach to AI is to list the first six Turing Award winners for AI: Marvin Minsky (1969) and John McCarthy (1971) for defining the foundations of the field based on representation and reasoning; Allen Newell and Herbert Simon (1975) for symbolic models of problem solving and human cognition; Ed Feigenbaum and Raj Reddy (1994) for developing expert systems that encode human knowledge to solve real-world problems. Although not comprehensive, we explored the flavor of logically and discretely finite methods that the software 1.0 approach to AI employed focused on natural language processing and computational linguistics by implementing pattern matching with ELIZA, compilation with LUNAR, and inference with CYC. There were many other earlier approaches to embedding machines with intelligence such as game playing, solving math problems, and ___, which can be found in the secondary resources listed in the bibliographic notes.

The remainder of the book is spent focused on the software 2.0 approach to AI: Judea Pearl (2011) for developing probabilistic reasoning techniques that deal with uncertainty in a principled manner; Yoshua Bengio, Geoffrey Hinton, and Yann LeCun (2019) for making “deep learning” (multilayer neural networks) a critical part of modern computing; and finally, Richard Sutton, Andrew Barto (2024) for pioneering reinforcement learning in which agents learn by maximizing reward via trial and error in which we will implement FFNs, CNN, RNNs, and GPTs.

A.7 Bibiliographic Notes

• The primary resources used throughout this chapter, as listed on the sidenotes, were (Weizenbaum 1966), a short paper on ELIZA; (Minsky 1968)’s anthology of dissertations from his doctoral students; (Winograd 1971) and (Woods 1972), doctoral dissertations for SHRDLU and LUNAR (the latter is a BBN report, based off his PhD thesis)
• For a historical perspective, refer to (Gardner 1958) and (Nilsson 2010)’s Part II (Chapter 6, 7), Part III (Chapter 11, 13), Part IV (Chapter 18), Part VII (Chapter 26);
• For classical natural language processing techniques including syntactic, semantic, and logical analysis, refer to (Eisenstein 2018)’s Chapter 9, 10, 11, 12, 13 and (Jurafsky and Martin 2026)’s Appendix E, F, G, H and (Russel and Norvig 2022)’s Part III (Chapter 7, 8, 9, 10) and Part VI (Chapter 24).

0.8 Problems

Intermezzo One: The Language of Sets, Functions, Logic

Fixed-Size DataA modified excerpt from How to Design Programs (Felleisen et al., 2014) Intermezzo 1: Beginning Student Language. Chapter 0 deals with BSL formal language theory and set theory as if it were a natural language. It introduces the “basic words” of the language (which in turn, models natural language), suggests how to compose “words” into “sentences,” and appeals to your knowledge of algebra sets as a collection of objects for an intuitive understanding of these “sentences.” While this kind of introduction works to some extent, truly effective communication requires some formal study.

Although these deterministic and finitely discrete methods of software 1.0 run into the Bitter Lesson — that is, describing a reality with too many parts to count — we will need the machinery that underlies such techniques, namely that of sets, functions, logic because the same machinery is the common unifying foundation for all of mathematics, including the set of stochastic and infinitely continuous mathematics we need for our journey up ahead with software 2.0. While we’ve introduced such languages of set theory, functions, and logic throughout chapter 0 by appealing to your intuition as a programmer, as per the opening exercept, truly effective communication and understanding requires the formalformal study of mathematics using the axiomaxiomatic method.

Historically speaking, (elements of euclid…)

The good news as a programmer is that you have an advantage to learning mathematics, because the essence of both activities are in fact one and the same with the Univalent FoundationsSee https://en.wikipedia.org/wiki/Univalent_foundations, and https://ncatlab.org/nlab/show/univalent+foundations+for+mathematics.

Let us begin.
You will understand in due time.

/-- Doubles a natural number. -/
def double (n : Nat) : Nat := n + n

theorem double_eq (n : Nat) : double n = 2 * n := by
  simp [double, Nat.two_mul]

#check And
#check Or
#check Or

#eval double 21

variable {α : Type*}
variable (s t u : Set α)
open Set

example (h : s ⊆ t) : s ∩ u ⊆ t ∩ u := by
  rw [subset_def, inter_def, inter_def]
  rw [subset_def] at h
  simp only [mem_setOf]
  rintro x ⟨xs, xu⟩
  exact ⟨h _ xs, xu⟩

example (h : s ⊆ t) : s ∩ u ⊆ t ∩ u := by
  simp only [subset_def, mem_inter_iff] at *
  rintro x ⟨xs, xu⟩
  exact ⟨h _ xs, xu⟩

Note

Because we are dealing with the domain of language, we will denote alphabets of symbols and strings of symbols with $w\in V$ and $\mathbf{s}=(w1,w2,\cdots ,w_t),w_i\in V$ respectively rather than $a\in \Sigma$ and $\mathbf{a}=(a1,a2,\cdots ,a_t),a_i\in \Sigma$ to denote the fact that our alphabets and strings are modeling vocabularies and sentences of words within the domain of language. The alphabet and string formalism of formal language theory can be applied to other domains that admit sequences of tokens i.e biology with protein folding.

Chapter 0 deals with formal language theory and set theory as if it were a natural language.

It introduces the “basic words” of the language, suggests how to compose “words” into “sentences,” and appeals to your knowledge of algebra for an intuitive understanding of these “sentences.” While this kind of introduction works to some extent, truly effective communication requires some formal study.

B. From Classical to Constructive Mathematics

In which we historically retrace the development of the foundations of mathematics, from the geometry of ancient greek mathematics, to the logicism and formalism of Göttingen, and finally, to the intuitionism and constructivism of the Valley.

B.1 Ancient Mathematics

B.2 Classical Mathematics

B.3 Constructive Mathematics

C. From Sequential to Parallel Processors

In which we historically retrace the development of processors from sequential to parallel processors