0
$\begingroup$

It is claimed that "lambda calculus is a universal model of computation that can be used to simulate any Turing machine". How can I, using this universal model, simulate an algorithm of calculating an algebraic sum of two numbers? How will this algorithm look, according to the grammar of the calculus, which does NOT include the + operator?

There is also a follow up question: may I introduce my own $X$-calculus, which would also be called a "universal model of computation" and will consist of a single letter $X$?

$\endgroup$

1 Answer 1

4
$\begingroup$

The lambda calculus not only has no + operator, but also lacks natural numbers. All it has are functions. The idea is to represent a natural as a specific function, and then define another addition-function to perform addition on said natural-functions (called numerals).

A natural number $n$ is represented as $\lambda sz. s(s(s(s \ldots z)))$ where there are exactly $n$ application of $s$ inside. Roughly, this representation makes $n$ to be written as a function operator that takes function $s$ and returns its $n$-th iterate $s^n = s \circ s \circ \ldots$.

After that, one can define a successor operation as $Succ = \lambda nsz. s(nsz)$. You can verify that reducing $Succ\ n$ when $n$ is a numeral will lead to the next numeral.

Similalrly, addition can be coded as repeated successor e.g. $Add = \lambda nm. n\ Succ\ m$. Again, one can verify that it operates as expected on numerals.

In this way we can walk a long run and slowly build all basic arithmetics and simulate natural numbers. We can also encode booleans, strings, and other standard data types using suitable functions. Eventually, we also define fixed point combinators that allow us to form recursive functions. After that we can write a lambda term that can simulate the execution of a Turing machine, so proving the Turing completeness of the language.

Regarding the question on the "X-calculus". Yes, you can definitely invent your model. You must define what are the "programs" in your model (e.g. the set of lambda terms, the set of Turing machines, the set of strings of the form $XXX\cdots$, etc.). Then you must associate them with a semantics. How do you run your programs? You need to define a semantic relation to formalize "this program computes this naturals-to-naturals function". After that, you have a model of computation and can check whether it's Turing powerful or not.

$\endgroup$
4
  • $\begingroup$ All of this would work if we agree that we represent natural numbers as "$n$ applications of $s$ inside"? This is not what is said in the calculus, right? It's an assumption to be made by us, if we want to use the calculus. $\endgroup$
    – yegor256
    Commented Feb 23, 2023 at 9:28
  • $\begingroup$ In other words, your summarization algorithm expects two functions as an input and returns another function as an output. In order to use this algorithm I have to encode integers first (turn them into functions) and decode them backward after the algorithm finishes (turn functions back to integers somehow). Do I get it right? $\endgroup$
    – yegor256
    Commented Feb 23, 2023 at 9:33
  • 2
    $\begingroup$ @yegor256 Indeed, that's not a part of the language, but a convention that we decide to adopt later on. Other representations are possible in the lambda calculus, we just pick this one because it seems one of the easiest to work with. In other formalisms we also often need to choose how to encode numbers: a Turing machine uses strings, and we can encode numbers there in many ways (binary, decimal, unary, ...) $\endgroup$
    – chi
    Commented Feb 23, 2023 at 9:33
  • 2
    $\begingroup$ @yegor256 Yes, you need to convert naturals to their representation (numeral-functions) and back. This is needed for all formalisms that do not have a primitive way to express naturals in the model. $\endgroup$
    – chi
    Commented Feb 23, 2023 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.