Lambda Calculus

Question 1

What form of computation did Turing propose?

Answer 1

Imperative programming which both humans and computers were capable of calculating through a set of unambiguous instructions.

Question 2

What was the Turing machine?

Answer 2

A finite tape that moves left and right based on whether a result is 1 or 0.

Question 3

What form of computation did Church propose?

Answer 3

Functional encoding (lambda calculus).

Question 4

What is the Turing-Church thesis?

Answer 4

The finding that both the Turing and Church computations give an equivalent output for the same input.

Question 5

What are the 4 components of Lambda Calculus? Define each…

Answer 5

Constants - Types of variables such as Integer, Float etc.
Variables - The value that the variables hold.
Application - Applying the function to the arguments.
Function - The body of the function.

Question 6

What are the 3 conversion rules?

Answer 6

Alpha - Converting the name of a variable across the entire function.
Beta - Converting input to output.
Eta - If functions are equivalent, the arguments can be dropped.