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.

Definition

Every word $p$ gives us a function called $[\![ p]\!]$ on words.

$[\![ 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 $[\![ p]\!] (x)$ is undefined.

Examples

$[\![\one\hash\hash ]\!](\one) \simeq \one\hash$.

$[\![\one\hash]\!](\hash\one) \simeq \hash\one\one$.

$[\![\hash]\!](\one)$ is undefined.

$[\![\one\hash\hash\hash\one\hash\hash\hash\hash]\!](x)$ is undefined for all $x$.

Attention

Instead of $[\![ p]\!](x)$, we might write $\phifn_{p}(x)$. This is a more common notation, actually. We use the “semantic bracket” notation because we frequently want to iterate the construction, having one program output a function which we then output run on some other input. For example,

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

Writing this with the “$\varphi$” notation, we have

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

This is a little harder to read.

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$, $[\![ p]\!](x)$ is undefined for all $x$.

For other programs $p$ there might be some programs $x$ for which $[\![ p]\!](x)$ is defined for some but not all input words.

Definition

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

\[ [\![ p]\!](x) \downarrow \]

if $[\![ p]\!](x)$ is defined. If $[\![ p]\!](x)$ is undefined, we write

\[ [\![ p]\!](x)\uparrow \]

The domain of $[\![ p]\!](x)$ is $\set{x : [\![ p]\!](x)(p)\dar}$.

Exercise 43

Find a program $q$ so that $[\![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 44

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 two or more arguments. Here is the relevant definition.

Definition

Every word $p$ gives us a function called $[\![p]\!]^n$ on $n$-tuples of words: for an $n$-tuple $\overline{x} = x_1, \ldots, x_n$,

\[ [\![p]\!]^n (\overline{x}) \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 $[\![ p]\!] (x)$ is undefined.

Example

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

Let $p$ be the program

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

Then $[\![ 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 45

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 46

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 $k\colon \words \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 $[\![ p]\!]$ of one argument, and then for each $n \geq 2$ we associated a function $[\![ p]\!]^n$ of $n$ arguments. This general definition works in case $n = 0$ also.

Definition

\[ [\![ p]\!]^0 (\ ) \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.

Usually we would drop the superscript $0$ and simply write $[\![ p]\!] (\ ) \simeq y$

1# computable partial functions#

At this point, we know that programs $p$ give rise to partial functions. So it is natural to ask about the collection of partial functions obtainable that are of the form $[\![ p ]\!]$ for some $p$.

Definition

A partial function $f:Words^n \to Words$ is $\one\hash$-computable if there is a program $p$ such that $f = [\![ p ]\!]^n$. This means that for all $n$-tuples of words $\overline{x} = x_1, \ldots, x_n$, $f(\overline{x}) \simeq [\![ p ]\!]^n(x)$.

Examples

(a) $f(x) = x$ is $\one\hash$-computable using the program $\one\hash\hash\hash$.

(b) $f(x) = x \one$ is $\one\hash$-computable using the program $\one\hash$.

(c) $f(x) = \one x$ is $\one\hash$-computable using the program $\moveprog_{1,2} + \one\hash + \moveprog_{2,1}$.

Exercise 47

Show that the following functions $f:\words\to\words$ are $\one\hash$-computable:

(a) $f(\one\hash) = \hash$, and otherwise, $f(x)\!\uparrow$.

(b) $f(x) = x + x$.

(c) $f(x) = \writeprog(x) + x$.

(d) $f(x) = \one^{|x|}$, where $|x|$ is the number of symbols in $x$.

(e) $f(x)$ as defined below:

\[\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}\]

Characteristic functions#

Definition

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} \one &\mbox{if $x\in A$} \\ \hash &\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 machine 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 6

Every finite set of words is a computable set.

Exercise 48

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 49

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

Exercise 50

(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

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

$W_p = \set{x : [\![ p]\!](x)\downarrow}$.

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

Exercise 51

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.

Functions defined by programs

Contents

Functions defined by programs#

Partial functions#

Functions of two or more arguments#

Functions of zero inputs#

1# computable partial functions#

Characteristic functions#

Computable sets and computably enumerable sets#

Equivalence of programs#