Dana Scott on Lambda Calculus

Prof. Dana Scott gave a few talks on Lambda Calculus, and some of them are available on Youtube.

A list of them can be found here:

Local Links
Video/Dana S. Scott Lambda Calculus, Then and Now
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 1) - λC 2018
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 2) - λC 2018
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 3) - λC 2018
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 4) - λC 2018
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 5) - λC 2018
Video/Dana Scott & Jeremy Siek - Theory & Models of Lambda Calculus: Typed and Untyped (Part 6) - λC 2018
Video/Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed - Part 1 of 5 - λC 2017
Video/Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed - Part 2 of 5 - λC 2017
Video/Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed - Part 3 of 5 - λC 2017
Video/Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed - Part 4 of 5 - λC 2017
Video/Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed - Part 5 of 5 - λC 2017
Video/Stochastic Lambda-Calculus

This video series seems to be taken in the same day, a total of 5 hours. Prof. Scott offered many anecdotal insights on how $\lambda$ calculus was invented and formed. It directly relates to the notion of function and combinators. Particularly, the SK Combinators.

Lecture 1

This starting lecture talks about the name of Lambda came from.

Lecture 2

Godel Numbering

Think about variables in terms of special numbers. This is an insight from Godel, and later utilized to created Universal computation.

We don't need Turing Machine

In this lecture, Scott explicitly stated that:

"You don't need Turing Machine to understand it, I hope I can convince you of that."

Scott's Universe is the Powerset of Integers

In this lecture, Scott explicitly stated that:

"The Universe if the Powerset of Integers."

Sophomores or Juniors should learn some Topology

Sophomores or juniors should have some topology from calculus...

A neighborhood of a possibly infinite set...

• The neighborhood of a possibly infinite set is just determined by a finite subset... and its complement
• A stronger topology, called product topology, where its complement can also be expressed with finite information... Hausdorf set taking half the topology

Once you define Topology, you may define continuous functions

• Define Continuous Functions
• The main difficulty is that there are two quantifiers, forming a rational number
• Finite amount of information can only be represented by a finite amount of rational numbers

Lecture 3

This lecture starts to mention the notion of algebraic closure and fixed points.

Drawing of Lattice

He mentioned that every undergraduate should learn to prove continuity in functions as an exercise.

This lecture mentioned three important persons in logic.

1. John Myhill
2. John Sheperdson
3. Hartley Rogers Jr.

Why he kicks himself in the middle of the night

This is also the place where he starts talking about the recursive combinators, and how this enumerative device can be used to make one rich and famous.

1. Here is where he wants to kick himself at the night
2. No body said: "do this operators have any algebra to them...", if only, if only ...

This statement relates to the paper on Algebra of Systems and this statement in particular..

A Concise Algebra for automating engineering tasks

This year 2009 paper summarized the following statement in the conclusion:

In Laws of programming, Hoare et al. questioned whether a small set of algebraic laws can be directly useful in a practical engineering design problem. The absence of a tool that can bridge the cognitive gap between mathematical abstractions and engineering problems may have been the main reason for their conservative attitude.

The above statement echos who Dana Scott was saying in the 2018 Lambda Conference.

A lookup table as a enumerable function

He said in this lecture:

If that lookup table is enumerable, that is a good definition of say that the enumeration operation is computable. ... So that computability here is on the same plane with enumerability.

Always think positively

He said the following:

Don't think of divergence and all of that. ... You can only achieve what can possibly achieve. Don't think of things that cannot be done. This is the way how enumeration works. Working with the positives. Of course, you can think of complementary sets.

This is also where one can starting relating to the laws of composition.

Lambda Calculus allows you to notate Least Fixed Points

There is a well-foundedness as he mentioned at about 39 minutes into this video. He started talking about . There is a connection between $lfp(x)$ or Least Fixed Point of $x$, and lambda calculus.

All Computable/Continuous Functions can be composed using Lambda Calculus

This where things get related to composition.

All Computable/Continuous Functions can be composed using Lambda Calculus and arithmetics. Arithmetics gives you the power of analyzing Gödel numbers and other kinds of structures.

Number 0,1 is related to K and S respectively

The arithmetic mechanism can be represented using SK Combinators, therefore, each can be related to a specific kind of number. The smaller numbers2, 3, 4 are assigned to do arithmetics.

Sub models with Closure Conditions within Computable Recursive Operators

There are ways to take closures in sub Lambad Calculus and iteration gives you recursive theory. It also allows one to filter out certain elements.

Closure is something can be expressed in Lambda Calculus.

Closed elements in the closed ... forms an algebra

Closed elements forms ... The last few minutes of lecture 3, Scott showed that there is a strong connection between algebra, complete lattice, upper/lower bounds as closure, and finally, fixed point.

Lecture 4

There are two uses of Close here.

1. Fixed Point Operator: Fixed Point of Something that cannot be fixed up anymore by C that is already fixed.
2. The Totality of Fixed Point of C form a Topological Space. In fact, it is the subspace of Power Set of $n$ with a power set of anthropology? In other words, it's a restriction on the topology of the power set of n- a topology on a sub lattice. And those topological spaces can be put together in at the category different closure operators give you different subspaces and continuous mapping between the subspaces that can be explained entirely in our lambda calculus.
3. Now the key thing her is: All computable continuous functions can be composed by using Lambda Calculus and arithmetic. Arithmetic gives you the possibility of analyzing Godel numbers as other kinds of structures. Lambda calculus only uses a fraction of the power of Godel numbering.
4. The basic operations of Lambda Calculus and arithmetic, when done over and over again, give you all recursively enumerable sets.
5. We can also think of doing these computations with resource limited means. Suppose you choose only Godel numbers that can fit into the state of Colorado, so you will only get a finite approximation to what you can do if you limit your Godel numbers.
6. I hate programming Turing machines, even Turing himself made a number of mistakes in his original paper that had to be corrected later. The programs are hard to write because of the very limited means of running back and forth on the tape to do Turing machines. But this is much less to write down..

1. Ross's found an improvement to Godel's incompleteness theorem. Barkley Rosser found an improvement to Godel's incompleteness theorem.
2. In an abstract way, closure is something you can express it nicely in Lambda Calculus. A closure operator is an operator such that from the generator $X$ you expand from the closure of $X$.
3. On these lattices, you can take the analogy of the Power set and make the fixed point of C a topological space and the Lambda Calculus gives you a notation for all the continuous functions between those lattices.
4. So you see: The Godel numbers give you the possibility of thinking of any kind of finite structure. But you can now look down at specialized structure, and special ways. And so these closure operators give you a way of doing a lot of that.

Lecture 5

1. But here is the crazy thing that Rosser discovered here: If you iterate iterating, what do you get? Exponential?