Further results on universal programs

Open In Colab

Further results on universal programs#

This section starts with a discussion of universal programs of more than one argument, a natural and important extension of what we have seen. It then moves to some observations about the particular universal program which we built, and also a fact about 1#-computable functions that falls out from our work on the universal program.

#@title
!python -m pip install -U setuptools
!python -m pip install -U git+https://github.com/lmoss/onesharp.git@main
from onesharp.interpreter.interpreter import *

Universal programs of more than one argument#

Here is a more general result based on what we have seen up to now.

Theorem 2

For every natural number \(n\) there is a program \(u_n\) such that for all words \(p\), \(x_1\), \(\ldots\), \(x_n\),

\[ [\![ u_n]\!](p,x_1, \ldots, x_n)\simeq [\![p]\!](x_1, \ldots, x_n) \]

What we have seen is an explicit program \(u_0\).

The proof of the general fact is an exercise using \(u_0\) and the \(s^m_n\) Theorem.

Exercise 69

Write a program trade which looks like it trades places with its input in R1. (Of course, a program cannot literally trade places with its input. But here is what we mean: running trade with p in R1 and all other registers empty does the same thing as running p with trade in R1 and all other registers empty.)

[Hint: You will need a universal program, and also an application of the Recursion Theorem.]

Exercise 70

Write a program self1 which writes itself to R1 but only uses R1 itself (no other registers). This exercise requires a trick, since there is no program like diag which only uses one register.

[Hint: you will need the technique of coding several registers into R1.]

An extra property of the universal program#

For use in several places, we need a technical remark about the universal prorgram \(u\) which we can arrange. That is, the remark below is not a consequence of the specification of \(u\) that we started with. It is not even a consequence of the outline of \(u\) which we provided. But if you write \(u\) the way we suggest, then the property below is either true, or one can arrange for it to hold.

Attention

We may take \(u\) to have the following property: when run on a word \(x\) in R1, the word in R1 is not empty at any point other than at the very end.

Only one work register#

A register machine program in our sense does not come with a number of how many arguments it expects. One and the same program can be used as a function of zero, one, two, or many arguments. In other words, the definition of \([\![p]\!]^n(x_1, \ldots, x_n)\) depends on \(n\) and of course on \(p\). Given \([\![p]\!]^n\) as a function of \(n\) arguments, we might ask how many registers are needed to compute it. We need the first \(n\) registers just to read the input. But are there functions which can be computed with two additional registers that cannot be computed with one? The work that we have recently seen shows that we can do with one additional register to do all the work.

Proposition 8

For every \(n\) and every program \(p\), there is a program \(q\) such that

  1. For all words \(x_1\), \(\ldots\), \(x_n\),

\[ [\![p]\!] (x_1, \ldots, x_n) \simeq [\![q]\!] (x_1, \ldots, x_n) \]

  1. \(q\) uses R1, \(\ldots\), R\(n\), R\((n+1)\), and no other registers.

  2. \(q\) may be obtained computably from \(p\) and \(n\).

Taking \(n = 0\), it shows that when running a register machine program \(p\) on no inputs, we may assume that the program uses only one register. In particular, we have an undecidability result:

Proposition 9

Let \(A\) be the set of register machine programs which are tidy and which only use R1.

Let \(K^1\) be \(\{ p \in A : [\![p]\!](\ )\!\!\downarrow\}\)

Then \(K_0 \leq_m K^1\).

We are going to prove that \(K_0\) is undecidable in the section on the halting problem. It follows from the last result that the halting problem for register machine programs which are tidy and which only use R1 is undecidable.

We are going to put the proposition just above to good use when we prove the undecidability of Post’s correspondence problem.

Now that we know that in a register machine architecture one can do with one work register, a next natural question would be whether any work registers are actually needed. For example, can one compute the \(f(x) = {\tt 1}x\) on a register machine using R1 only? Intuitively, one should not be able to do this. (Try it and see.) In fact, it is possible to show this fact. See the paper Confusion of Memory for details.

Contents