in Books, Doing Books, Theory of Computation

Theory of Computation #16

Exercise 4.1.1: What is the result of applying the function ( pi(2,2) x pi(2,1)) o (pi(3,1) x pi(3,3)) to the three-tuple (5,4,7)?

The function pi(x,y) returns the yth element of an x-tuple. x is the combinator and o the composition. Therefore we first get (5, 7) which is then put into the first pi tuple to return (7,5).

Exercise 4.1.2: If f: N -> N is defined by

what is the value of f(3)?

So, C() returns 0. and u adds one to its input.

Let’s see, f(3) expands the following way:

and now reduces to:


Exercise 4.5.2P: Write an interpreter for the bare-bones programming language in this chapter.

The bare-bones programming language consists of just three statements. There is:

  • incr name; which increases name by one
  • decr name; which decreases name by one, but only to 0
  • while name /= 0 do; … end; which repeats the statements between do and end until name is zero.

This language fulfills the Church-Turing thesis, i.e. it is Turing-complete but more based on the lambda calculus idea.

Here’s what will happen: We will input a string – our source code – into our program. It will create variables, I will set them to 0 automatically. And then it can start applying these statements. Let’s see how we do it.

My first idea is that we take a hash-map for our variables. They will be dynamically bound, i.e. global.

But before we can create variables, we need to parse the input. Let’s take this simple program as our test program:

This program sets i to 2 and then j to 2. That is, the end state should look like {“i” 2 “j” 2}.

The first thing I want is each statement individually:

That’s pretty easy:

Next part tomorrow

Write a Comment