## (4,3): The First Code
### Or: The Compilation from Laws to Numbers
> _In the year 1930, the realization of an actual physical device that could function as a general-purpose information-processing programmable computer was still decades in the future. Yet someone knowledgeable about modern programming languages today looking at Gödel’s paper on undecidability written that year will see a sequence of 45 numbered formulas that looks very much like a computer program._
> -Martin Davis
> _Something like primes._
> -Leibniz, paraphrased.
---
0: Ok so, to really understand Gödel's definition, it's not enough to just talk about it.
1: Coming from someone who talks as much as you do, that's saying a---
0: Talking wasn't Gödel's style. So in this file we're gonna stop talking and shut up and be curt.
1: Great! Let's be---
0: No talking.
It's time to be curt, and speak the language of Gödel.
_(Narrator: The file falls silent, as the surrounding format becomes monospaced...)_
```python
# =================================
# Gödel's Definition of Computation
#
# The built-in functions of μ-lang.
# =================================
and_gödel_said = """
We now insert a parenthetic consideration that for the
present has nothing to do with the formal system P.
"""
# 1: What's P?
# 0: Principia Mathematica.
# 1: The crazy Russell book no one reads?
# 0: Yeah.
# 1: How am I supposed to follow this if I don't know
# anything about that system?
# 0: He just said it has nothing to do with that.
# Just be quiet and follow me.
and_gödel_said += """
First we give the following definition:
A number-theoretic function φ(x₁, x₂,... , xₙ) is said to
be recursively defined in terms of the number-theoretic
functions ψ(x₁, x₂, …, xₙ₋₁) and μ(x₁, x₂, …, xₙ₊₁) if
φ(0, x₂, …, xₙ) = ψ(x₂, …, xₙ),
φ(k + 1, x₂, …, xₙ) = μ(k, φ(k, x₂, …, xₙ), x₂, …, xₙ)
hold for all x₂, …, xₙ, k.
"""
# 1: What the hell was all that?
# 0: He's just defining recursion.
# 1: Was that the definition we've been waiting for?
# 0: No, that's just the setup.
# 1: Why was it so complicated?
# 0: It's simpler than it looks. Would you
# understand if he'd said this?
and_zero_said = """
A function from ints to ints f(m, n) is said to
be recursively defined in terms of the functions
g(n) and h(m, n, o) if
f(0, n) = g(n)
f(m + 1, n) = h(m, n, f(m, n))
for all m and n.
"""
# 1: Of course that's just recursion.
# 0: Gödel's just doing that with *args
# 1: Like pointers to args?
# 0: No I mean functions that take a variable
# number of arguments.
# 1: Ah gotcha.
# 0: Ok back to Gödel.
and_gödel_said += """
A number-theoretic function φ is said to be recursive
"""
# 0: Here comes the definition.
# 1: Shh, I can't hear it!
and_gödel_said += """
if there is a finite sequence of number-theoretic functions
φ₁, φ₂, …, φₙ that ends with φ and has the property that every
function φₖ of the sequence is recursively defined in terms of
two of the preceding functions, or results from any of the
preceding functions by substitution, or, finally, is a constant
or the successor function x + 1.
"""
# 1: Was that it?
# 0: Yep!
# 1: That didn't even feel like a definition.
# 0: Why not?
# 1: I have some questions. Can we translate this into something more precise?
# 0: Of course. Follow me.
```
1: Wait why are we outside of the code? I said _more_ precise.
0: Just coming up for some air. Ok, what's the question?
1: I'm not sure what Gödel means.
0: You understand recursion right?
1: Of course Zero, I'm a professional developer.
0: So what's the issue?
1: What's a constant function?
0: Oh c'mon you know what a constant function is.
1: I know what it usually means. I want to know what Gödel means.
0: He just means "constant."
1: Zero don't be dumb.
0: How is this "dumb"?
1: Show me what Gödel means by constant.
0: Here's one:
```python
def constant(n):
return k
```
1: What's $k$.
0: It's a constant.
1: Where did you get it from?
0: What?
1: Is it a constant or a variable?
0: A constant.
1: Ok, which number is it?
0: We haven't decided. It's unspecified.
1: HOW IS THAT NOT A VARIABLE?
0: What's the problem?
1: Do a simpler function. No free constant-y variable-ish things.
0: Ok, here:
```python
def five(n):
return 5
```
1: Where did you get that $5$ from?
0: From the number five. It's five.
1: ZERO DON'T BE DUMB.
0: How can I help?
1: Zero, we just got done with Church's system where we had to implement literally everything, including numbers.
And the implementation of numbers wasn't like "totally obvious."
We had to think for a while.
And when we got a definition we were happy with, numbers like 0 and 1 ended up being _two argument functions._ Or one argument functions that returned one argument functions that returned -- not numbers -- but the first argument applied "number-many-times" to the second one.
That was weird.
And it kinda messed with my head at first.
But once I understood it, I felt like I understood a lot about the mindset of the people like Church and Gödel who create these systems.
In these low level systems, we have to implement everything from scratch.
Like we have literally nothing except what we explicitly build-in when we define the system.
Absolutely nothing else exists. So whenever we want a thing, we have to build it step-by-step, without skipping steps, from the bare bones built-ins of whatever system we're in.
0: What's the question?
1: Well after all that, I don't think it's unreasonable for me to be not-entirely-sure what Gödel means by words like "constant"!
0: Can you ask a more specific question?
1: Is this a constant function in Gödel's definition?
```python
def what(n):
return n
```
0: No, that's the identity.
1: He didn't say if the identity is recursive.
0: It's obviously recursive.
1: Is the original paper this imprecise?
0: I dunno, never read it.
1: Well I think we need to.
0: Read Gödel's paper?
1: Read Gödel's paper. Or else I'm gonna keep being confused about whether or not I'm confused.
---
TODO: Before we go to the next file, start reading the Godel paper and justify these definitions:
---
![[godel-1931-paper-00.jpg]]
![[godel-1931-paper-01.jpg]]
![[godel-1931-paper-03.jpg]]
![[godel-1931-paper-04.jpg]]
```python
"""
The 46 formulas in Godel's 1931 paper.
"""
# Godel numbering for individual symbols,
# not counting variables, which will be
# represented as various powers of primes
# bigger than 13, as in the original paper.
Ord = {
'0': 1,
'f': 3,
'~': 5,
'∨': 7,
'Π': 9,
'(': 11,
')': 13,
}
Chr = {v:k for k,v in Ord.items()}
def Eps(max, pred):
""" Gödel's name for what eventually becomes the μ operator. """
y = 0
while y <= max:
if pred(y):
return y
y += 1
else:
return 0
```