Functions defined by programs

Functions defined by programs¶

At this point we know what programs of $\one\hash$ are and how they work. We are interested not just in the programs themselves but in what they compute.

We call the set $\set{\one,\hash}$ our alphabet, and we use the letter $A$ for it.

We know that it is odd to call such a small set an “alphabet”, even more so when that set doesn’t have any letters in it! But this usage is standard, and so we’ll adopt it. When used in situations like ours, the word “alphabet” just means a set that you use to build words from.

But if $\set{\one,\hash}$ is our alphabet, what in the world are our words?!

Answer: A word is just a sequence of symbols from our alphabet.

(In contrast to most uses in mathematics and computer science, our words will all be non-empty, unless we say otherwise.

Examples of words include $\one\one\hash$, and also $\hash\hash\hash$.

Let us be clear about the difference between instructions and programs:

Instructions are single steps in programs.

A program of $\one\hash$ is just a sequence of instructions, run together to make a big word. An instruction counts as a program, but programs of length $\geq 2$ are not instructions.

Definition 2

Every word $p$ gives us a function called $\phifn_p$ on words.

$\phifn_p (x) \simeq y$ means that $p$ is a program, and when we run it $p$ with the word $x$ in $\Rone$ and all other registers empty, the register machine eventually halts with $y$ in $\Rone$ and all other registers empty.

In all other cases (if $p$ isn’t a program, or if $p$ does not halt with $x$ in $\Rone$, or if $p$ halts but not all of the registers besides $\Rone$ are empty), then we say that $\phifn_p (x)$ is undefined.

Examples

$\phifn_{\one\hash\hash}(\one) \simeq \one\hash$.

$\phifn_{\one\hash}(\hash\one) \simeq\hash\one\one$.

$\phifn_{\hash}(\one)$ is undefined

$\phifn_{\one\hash\hash\hash\one\hash\hash\hash\hash}(x)$ is undefined for all $x$.

Attention

Instead of $\phifn_p(x)$, we might write $\semantics{p}(x)$. We do this especially when we want to iterate the construction. That is, instead of writing

\[\phifn_{\phifn_{\one\hash\hash}(\one)}(\hash\one) \simeq \hash\one\one. \]

we would prefer to write

\[\semantics{\semantics{\one\hash\hash}(\one)}(\hash\one)\simeq \hash\one\one. \]

In this notation, $\semantics{p}$ is a function, just like $\phifn_p$ is in the other notation.

Exercise 14

Show that the following function $f:\words\to\words$ is $\one\hash$-computable: $f(x) = \writeprog(x) + x$.

Partial functions¶

Suppose we run a program $p$ with an input word $x$ in R1 and all other registers empty. This run might, or might not, halt. The first example of this is when $p$ is a loop $\one\hash^3\one\hash^4$. For this program $p$, $\phifn_p(x)$ is undefined for all $x$.

For other programs $q$ there might be some programs $p$ for which $\phifn_p$ is defined for some but not all input words.

Definition

Given words $x$ and $y$, we write

\[ \phifn_x(y)\downarrow \]

if $\phifn_x(y)$ is defined. If $\phifn_x(y)$ is undefined, we write

\[ \phifn_x(y)\uparrow \]

The domain of $\phifn_x$ is $\set{y : \phifn_x(p)\dar}$.

Exercise 15

Find a program $q$ so that $\phi_q(x)\downarrow$ iff the number of symbols in $x$ is an even number.

It is useful to be a litte more abstract. In general in mathematics, functions are almost always total; that is, they are almost always defined for all possible inputs. In computability theory this is not so. We deal with functions that are frequently partial. This means that they are undefined for some, or even all, of their possible inputs.

Working with partial functions adds a slight conceptual overhead to working with functions in general. If $f: Y \to Z$ and $g: X\to Y$ are partial functions, then the composition

\[ f \o g : X \to Z \]

is also a partial function. When we write

\[ (f\o g)(x) \simeq z \]

we mean that there is some $y\in Y$ such that $g(x)\simeq y$ and $f(y)\simeq z$. In particular, we only use the notation $(f\o g)(x) \simeq z$ when $g(x)\dar$.

We have mentioned monoids in connection with the $+$ operation on words. Here is another monoid. Let $P$ be the set of partial functions from words to words. Let $id$ be the identity function on words. Then we have a monoid

\[ (P, \o, \id) \]

Exercise 16

Find a monoid homomorphism $h: (\words, + , \eps) \to (P,\o,\id)$.

Functions of two or more arguments¶

A program $p$ of $\one\hash$ can also be used as a function of two or more arguments. Here is the relevant definition.

Definition 3

Every word $p$ gives us a function called $\phifn^n_p$ on $n$-tuples words.

$\phifn^n_p (x_1,\ldots, x_n) \simeq y$ means that $p$ is a program, and when we run it $p$ with $x_i$ in register $i$ (for $1\leq i \leq n$) and all other registers empty, then the register machine eventually halts with $y$ in $\Rone$ and all other registers empty.

In all other cases (if $p$ isn’t a program, or if $p$ does not halt when run on $x$, or if $p$ does halt when run on $x$ but upon halting, not all of the registers besides $\Rone$ are empty), then we say that $\phifn_p (x)$ is undefined.

Examples

$\phifn^0_{\one\hash}(\ ) \simeq \one$.

$\semantics{\moveprogtwoone}(\one,\hash\hash\one) \simeq \one\hash\hash\one$.

Let $p$ be the program

\[ \clearprog_1 + \clearprog_3 + \moveprog_{2,1} \]

Then $\phifn_p^3(x,y,z) \simeq y$ for all words $x$, $y$, $z$. (Here $\clearprog_1$ and $\clearprog_3$ are programs that simply delete all the symbols in those registers. We have seen $\clearprog_1$, and $\clearprog_3$ is similar.)

Exercise 17

For some purposes, the notion of $\semantics{p}^n$ is not what one wants. Here is an alternative. We say that

\[ \semanticsalt{p}^n(x_1, \ldots, x_n) \simeq y \]

if $p$ is a program, and running it with $x_1$ in $\Rone$, $\ldots$, $x_n$ in $Rn$, and all othe registers empty eventually comes to a halt with $x_1$ in $\Rone$, $\ldots$, $x_n$ in $Rn$ (so the inputs are preserved), and $y$ in register $n+1$.

(a) Prove that for every $p$ there is some $q$ so that $\semantics{p}^n \simeq \semanticsalt{q}^n$.

(b) Prove that for every $q$ there is some $p$ so that $\semantics{p}^n \simeq \semanticsalt{q}^n$.

Exercise 18

Here is an example that shows that sometimes $\semanticsalt{\ }$ is more useful than $\semantics{ \ }$. Suppose we have three computable functions:

\[\begin{split} \begin{array}{l} f: \words^2 \to \words \\ g: \words \to \words \\ h: \words \to \words \\ \end{array} \end{split}\]

Define a new function $f: \words^2 \to \words$ by composition in the following form.

\[ k(x) = f(g(x), h(x)) \]

Show that if $f$, $g$, and $h$, are all $\one\hash$-computable, so is $k$.

Functions of zero inputs¶

We started by associating to each program $p$ a function $\phifn_p$ of one argument, and then for each $n \geq 2$ we associated a function $\phifn_p^n$ of $n$ arguments. This general definition works in case $n = 0$ also. For the record:

$\phifn^0_p (\ ) \simeq y$ means that $p$ is a program, and when we run it $p$ with all registers empty, the register machine eventually halts with $y$ in $\Rone$ and all other registers empty.

For example, $\phifn_{\one\hash}(\ ) \simeq \one$.

Characteristic functions¶

Definition

A set $A\subseteq \words$ is $\one\hash$-computable if $\chi_A$ is a computable function. Other names for “computable” include “decidable” and “recursive”.

Important

Our work will also involve other notions of “computable” besides $\one\hash$-computability. For example, we’ll see intuitive computability, Turing maching computability, Python computability, and other notions besides. So it will be important to keep these straight. This is why we put the “$\one\hash$” in the name “$\one\hash$-computable”. But at this stage, the notion which we’ll study the most is $\one\hash$-computability.

Exercise 19

Let $A$ and $B$ be $\one\hash$-computable sets. Show that $A\cap B$, $A\cup B$, and $\overline{A}$ are also $\one\hash$-computable, where

\[\begin{split} \begin{array}{lcl} A\cap B & = & \set{w \in \words : w\in A \mbox{ and } w\in B} \\ A\cup B & = & \set{w \in \words : w\in A \mbox{ or } w\in B \mbox{ (or both)}} \\ \overline{A} & = & \set{w\in \words : w\notin A} \\ \end{array} \end{split}\]

Exercise 20

Is the set of $\one\hash$ programs a $\one\hash$-computable set of words?

Exercise 21

Show that the following function is $\one\hash$-computable:

\[\begin{split} f(w) = \left\{ \begin{array}{ll} w & \mbox{if every symbol in $w$ is $\one$}\\ \hash & \mbox{otherwise} \end{array} \right. \end{split}\]

Exercise 22

(a) As a parallel to how we defined $\one\hash$-computability, define what it means for a function from words to words to be Python-computable

(b) There is a Python program called onesharp which takes two arguments, a $\one\hash$ program and a finite sequence of $\one\hash$-words. Assuming that onesharp behaves correctly, show that every $\one\hash$-computable function is Python computable.

[Hint: you will need to say clearly what “behaves correctly” means.]

Computably enumerable sets¶

Definition 4

Let $p$ be a program. We write $W_p$ for the domain of $\phifn_p$. That is,

$W_p = \set{x : \phifn_p(x)\downarrow}$.

A set $A\subseteq\words$ is computably enumerable if there is some program $p$ such that $A = W_p$.

Exercise 23

Show that every computable set is computably enumerable. (As we shall see, the converse is false.). Show also that the family of computably enumerable sets is closed under intersection: if $A$ and $B$ are computably enumerable, so is $A\cap B$.

When does a program halt?

Tidy programs

Invitation to Computability