https://youtu.be/AbK4bZhUk48
text § 5.3

there's one bit of mystery left: we've been blithely consing, always
assuming there's another one

what is the glue the data structure is made of?

gödel check!!

he invented a way of encoding complicated expressions with numbers.
see: GEB

gjs can implement cons with numbers

(cons x y) ⇒ 2^x ⋅ 3^y
(car x)    ⇒ number of factors of 2 in x
(cdr x)    ⇒ number of factors of 3 in x

"this is fine except the numbers quickly become larger in digits than
the number of protons in the universe"

how do we impose our lisp tree structure on a linear memory structure?

a classic way of storing list structure in linear memory is with the
method of dividing memory into two arrays: the-cars and the-cdrs

each memory cell contains an object describing type of data and the
piece of data which can be a pointer to another cell

the only problem left is we don't have infinite memory

–> break

"10 to the 14th is not a very large number!"
–gjs

the illusion of infinity can be arranged:
whenever you look the thing is there

a computer or person can only look a finite number of times

"users produce garbage"
–gjs

there must be some way to reclaim garbage

if you trace every piece of data that is connected to by the
registers, anything not marked in that trace will be garbage

"bang!"
–gjs

this was the mark-and-sweep gc program used on the DEC PDP-6.

a faster better gc program is using the from-space/to-space method
where you copy the useful stuff back and forth between the two blocks
of memory, leaving behind "broken hearts"

all reasonable garbage collectors are small

–> break

we've dazzled you with some things you'd like to compute

are there things you can't compute? yes.

you can't analyze an arbitrary program to determine if it is an
infinite loop (the halting problem?)

this procedure safe? cannot be implemented (related to cantor's
diagonal argument)

yes, the halting theorem. and with the halting theorem, we will halt.

is this the last question?

…

apparently so.

(fin)