Functions defined by programs

Functions defined by programs#

At this point we know what programs of 1# are and how they work. We are interested not just in the programs themselves but in what they compute.

We call the set {1,#} 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 {1,#} is our alphabet, what in the world are our words?!

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

Examples of words include 11#11#### and also the empty word $\varepsilon$.

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

Instructions are single steps in programs.

A program of 1# 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 6

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 29

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 7

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 30

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 \circ g : X \to Z \]

is also a partial function. When we write

\[ (f\circ 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, \circ, \id) \]

Exercise 31

Find three programs $p$, $q$, and $r$ such that $[\![p]\!](q)$, $[\![[\![p]\!](q)]\!](r)$, $[\![q]\!](r)$, and $[\![p]\!]([\![q]\!](r))$ are all defined, and yet

\[ [\![[\![p]\!](q)]\!](r) \neq [\![p]\!]([\![q]\!](r)) \]

Functions of two or more arguments#

A program $p$ of 1# can also be used as a function of zero or more arguments. Here is the relevant definition.

Definition 8

Every word $p$ gives us a function called $\phifn^n_p$ on $n$-tuples of 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 R$i$ (for $1\leq i \leq n$) and all other registers empty, then the register machine eventually halts with $y$ in R1 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 R1 are empty), then we say that $\phifn_p (x)$ is undefined.

Examples

$\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.)

Attention

Programs in 1# do not come with an “arity”. It is natural to think of a program as a function of the registers $i$ such that 1^i #^5 is an instruction in it. But our definitions do not require this. They allow every program to be used as a function of one or more numbers of variables. For example if $p$ is clear_2 + clear_3, then we have

$[\![ p ]\!]^1(1) = 1$.
$[\![ p ]\!]^2(\#,1) = \#$.
$[\![ p ]\!]^3(1,\#,1) = 1$.

Exercise 32

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$.

(c) Show that we can go computably from $p$ to $q$, and vice-versa.

Exercise 33

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.

Definition 9

\[ \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 R1 and all other registers empty.

Characteristic functions#

Definition 10

For any set $A$, the characteristic function of $A$ is the function $\chi_A$ given by

\[\begin{split} \chi_A(x) = \left\{ \begin{array}{ll} 1 &\mbox{if $x\in A$} \\ 0 &\mbox{if $x\notin A$} \end{array}\right. \end{split}\]

A set $A\subseteq \words$ is 1#-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 1#-computability.
We have already seen intuitive computability, and this is not exactly a mathematical concept. But we will see Turing maching computability, Python computability, and other notions besides. So it will be important to keep these straight. This is why we put the 1# in the name “1# -computable”.

The notion which we’ll study the most is 1# -computability.

Proposition 2

Every finite set of words is a computable set.

Exercise 34

Let $A$ and $B$ be 1#-computable sets. Show that $A\cap B$, $A\cup B$, and $\overline{A}$ are also 1#-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 35

Is the set of 1# programs a 1#-computable set of words?

Exercise 36

Show that the following function is 1#-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 37

(a) As a parallel to how we defined 1#-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 1# program and a finite sequence of 1# -words. Assuming that onesharp behaves correctly, show that every 1# -computable function is Python computable.

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

Computable sets and computably enumerable sets#

We have seen above the definition of a computable set of words. We now have a definition which is different but related. Both concepts are important in computability theory.

Definition 11

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 38

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$.

Equivalence of programs#

Definition

Two programs $p$ and $q$ are equal if they are identical symbol-by-symbol.

They are strongly equivalent if whenever they are started on the same words in all registers, if one halts so does the other, and all register contents are the same at the halt.

The are equivalent as one-place functions if $[\![p]\!]$ and $[\![q]\!]$ are the same partial function. That is, for all $x$, $[\![p]\!](x) \simeq [\![q]\!](x)$.

More generally, we could define the notion of equivalent as $n$-place functions for all natural numbers $n$.

For example, 1### and 1###1### are not equal, but they are strongly equivalent (and thus equivalent as one-place functions).

For an example of programs $p$ and $q$ which are equivalent as one-place functions but not strongly equivalent, let $p$ be 1#, and let $q$ be clear_2 + 1#. Running $q$ when R1 and R2 both have 1 results in a halting computation where R1 has 11 and R2 is empty. But running $p$ this way preserves R2.