{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "metadata": { "id": "nsBwZKyT_lo1" }, "source": [ "# Functions defined by programs" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "kagQ3xd6nzIL" }, "source": [ "\n", "At this point we know what programs of ```1#``` are and how they work.\n", "We are interested not just in the programs themselves\n", "but in *what* they compute. \n", "\n", "We call the set ```{1,#}``` our *alphabet*, and we use the letter $A$ for it.\n", "\n", "\n", "We know that it is odd to call such a small set an \"alphabet\",\n", "even more so when that set doesn't have any letters in it!\n", "But this usage is standard, and so we'll adopt it.\n", "When used in situations like ours, the word \"alphabet\"\n", "just means a set that you use to build words from. \n", "\n", "But if ```{1,#}``` is our alphabet, what in\n", "the world are our words?!\n", "\n", "Answer:\n", "A *word* is just a sequence of symbols from our alphabet.\n", "\n", " Examples of words include \n", "```11#11####``` and also the empty word $\\varepsilon$.\n", "\n", " \n", "Let us be clear about the difference between\n", "*instructions* and *programs*: \n", " \n", "*Instructions* are single steps\n", "in programs. \n", " \n", "\n", " \n", "A *program* of ```1#``` is just a sequence of\n", "instructions, \n", "run together to make a big word.\n", "An instruction counts as a program, \n", "but programs of length $\\geq 2$ are not instructions.\n", "\n", "\n", "\n", "```{prf:definition}\n", ":label: phi-notation\n", "Every word $p$ gives us a function\n", "called $\\phifn_p$ on words. \n", "\n", "$\\phifn_p (x) \\simeq y$ means that\n", " $p$ is a program,\n", " and\n", "when we \n", "run it\n", "$p$ with the word $x$ in $\\Rone$ and all other registers empty,\n", "the register machine \n", "eventually halts with $y$ in $\\Rone$ and all other \n", "registers \n", "empty. \n", " \n", " \n", "In all other cases \n", "(if $p$ isn't a program, \n", "or if $p$ does not halt with $x$ in $\\Rone$, \n", "or if\n", "$p$ halts but not all of the registers besides $\\Rone$ are empty),\n", "then we say that $\\phifn_p (x)$\n", "is *undefined*.\n", "```\n", "\n", "\n", "```{admonition} Examples\n", ":class: tip\n", "\n", "$\\phifn_{\\one\\hash\\hash}(\\one) \\simeq \\one\\hash$.\n", "\n", "$\\phifn_{\\one\\hash}(\\hash\\one) \\simeq\\hash\\one\\one$.\n", "\n", "$\\phifn_{\\hash}(\\one)$ is undefined\n", "\n", "$\\phifn_{\\one\\hash\\hash\\hash\\one\\hash\\hash\\hash\\hash}(x)$ is undefined for all $x$.\n", "```\n", "\n", "\n", "\n", "\n", "\n", "```{attention} \n", "Instead of $\\phifn_p(x)$, we might write $\\semantics{p}(x)$.\n", "We do this especially when we want to iterate the construction.\n", "That is, instead of writing\n", "\n", "$$\\phifn_{\\phifn_{\\one\\hash\\hash}(\\one)}(\\hash\\one)\n", "\\simeq \\hash\\one\\one.\n", "$$\n", " \n", "we would prefer to write\n", "\n", "$$\\semantics{\\semantics{\\one\\hash\\hash}(\\one)}(\\hash\\one)\\simeq \\hash\\one\\one.\n", "$$\n", "``` \n", "In this notation, $\\semantics{p}$ is a function,\n", "just like $\\phifn_p$ is in the other notation.\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "J6Cgei7XpU_7" }, "source": [ "```{exercise} \n", "\n", "Show that the following function $f:\\words\\to\\words$ is $\\one\\hash$-computable: $f(x) = \\writeprog(x) + x$.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ZhaXDhZfFra5" }, "source": [ "# Partial functions\n", "\n", "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$.\n", " \n", "For other programs $q$ there might be some programs $p$ for which $\\phifn_p$ is defined for some but not all input words. \n", "\n", "```{prf:definition}\n", "\n", "Given words $x$ and $y$, we write\n", "\n", "$$\n", "\\phifn_x(y)\\downarrow\n", "$$\n", "\n", "if $\\phifn_x(y)$ is defined. If $\\phifn_x(y)$ is undefined, we write\n", "\n", "\n", "$$\n", "\\phifn_x(y)\\uparrow\n", "$$\n", "\n", "The *domain* of $\\phifn_x$ is $\\set{y : \\phifn_x(p)\\dar}$.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "tM526JqM5b2x" }, "source": [ "```{exercise}\n", "Find a program $q$ so that $\\phi_q(x)\\downarrow$ iff the number of symbols in $x$ is an even number.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "eUs3PkdU0kab" }, "source": [ "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. \n", "\n", "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 \n", "\n", "$$\n", "f \\circ g : X \\to Z\n", "$$\n", "\n", "is also a partial function. When we write \n", "\n", "$$\n", "(f\\circ g)(x) \\simeq z\n", "$$\n", "\n", "we mean that there is some $y\\in Y$ such that $g(x)\\simeq y$\n", "and $f(y)\\simeq z$. In particular, we only use the notation $(f\\o g)(x) \\simeq z$ when $g(x)\\dar$. " ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "9XvPQoa1nAnd" }, "source": [ "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\n", "\n", "$$\n", "(P, \\circ, \\id)\n", "$$" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{exercise}\n", "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\n", "\n", "$$\n", "[\\![[\\![p]\\!](q)]\\!](r) \\neq [\\![p]\\!]([\\![q]\\!](r))\n", "$$\n", "```\n", "\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "PQzllCr-Fu2y" }, "source": [ "# Functions of two or more arguments\n", "\n", "A program $p$ of ```1#``` can also be used as a function of zero or more arguments. Here is the relevant definition.\n", "\n", "\n", "```{prf:definition}\n", ":class: tip\n", "\n", "Every word $p$ gives us a function\n", "called $\\phifn^n_p$ on $n$-tuples of words. \n", "\n", "$$\n", "\\phifn^n_p (x_1,\\ldots, x_n) \\simeq y\n", "$$\n", "\n", "means that\n", " $p$ is a program,\n", " and\n", "when we \n", "run it\n", "$p$ with $x_i$ in R$i$ (for $1\\leq i \\leq n$) and all other registers empty,\n", "then the register machine \n", "eventually halts with $y$ in R1 and all other \n", "registers \n", "empty. \n", " \n", " \n", "In all other cases \n", "(if $p$ isn't a program, \n", "or if $p$ does not halt when run on $x$, \n", "or if\n", "$p$ does halt when run on $x$\n", " but upon halting, not all of the registers besides R1 are empty),\n", "then we say that $\\phifn_p (x)$\n", "is *undefined*.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "pryZwxIMf1In" }, "source": [ "\n", "\n", "```{admonition} Examples\n", ":class: tip\n", "\n", "\n", "$\\semantics{\\moveprogtwoone}(\\one,\\hash\\hash\\one) \\simeq\n", "\\one\\hash\\hash\\one$.\n", "\n", "Let $p$ be the program\n", "\n", "$$\n", "\\clearprog_1 + \\clearprog_3 + \\moveprog_{2,1}\n", "$$\n", "\n", "Then $\\phifn_p^3(x,y,z) \\simeq y$ for all words $x$, $y$, $z$.\n", "(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.)\n", "\n", "```\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "```{attention} \n", "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\n", "\n", "1. $[\\![ p ]\\!]^1(1) = 1$.\n", "\n", "2. $[\\![ p ]\\!]^2(\\#,1) = \\#$.\n", "\n", "3. $[\\![ p ]\\!]^3(1,\\#,1) = 1$.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "FaUfdoaBWFi-" }, "source": [ "```{exercise}\n", "For some purposes, the notion of $\\semantics{p}^n$ is not what one wants. Here is an alternative. We say that \n", "\n", "$$\n", "\\semanticsalt{p}^n(x_1, \\ldots, x_n) \\simeq y\n", "$$\n", "\n", "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$.\n", "\n", "(a) Prove that for every $p$ there is some $q$ so that $\\semantics{p}^n \\simeq \\semanticsalt{q}^n$.\n", "\n", "(b) Prove that for every $q$ there is some $p$ so that $\\semantics{p}^n \\simeq \\semanticsalt{q}^n$.\n", "\n", "(c) Show that we can go computably from $p$ to $q$, and vice-versa.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "G_7muitJoUEd" }, "source": [ "```{exercise}\n", "Here is an example that shows that sometimes $\\semanticsalt{\\ }$ is more useful than $\\semantics{ \\ }$. Suppose we have three computable functions:\n", "\n", "$$\n", "\\begin{array}{l}\n", "f: \\words^2 \\to \\words \\\\\n", "g: \\words \\to \\words \\\\\n", "h: \\words \\to \\words \\\\\n", "\\end{array}\n", "$$\n", "\n", "Define a new function $f: \\words^2 \\to \\words$ by composition in the following form.\n", "\n", "$$\n", "k(x) = f(g(x), h(x))\n", "$$\n", "\n", "Show that if $f$, $g$, and $h$, are all $\\one\\hash$-computable, so is $k$.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "WOy1_0mpgsJ9" }, "source": [ "# Functions of zero inputs\n", "\n", "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. " ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{prf:definition}\n", "$$\n", "\\phifn^0_p (\\ ) \\simeq y\n", "$$\n", "\n", "means that\n", " $p$ is a program,\n", " and\n", "when we \n", "run it\n", "$p$ with\n", "all registers empty, the register machine \n", "eventually halts with $y$ in R1 and all other \n", "registers \n", "empty. \n", "```\n" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{example}\n", "$\\phifn^0_{\\one\\hash}(\\ ) \\simeq \\one$.\n", "\n", "$[\\![[\\![```write```]\\!](```##1```)]\\!]( ) \\simeq ```##1```.\n", "```" ] }, { "cell_type": "markdown", "metadata": { "id": "klf9a2FvgnPu" }, "source": [ "# Characteristic functions\n", "\n", "\n", "```{definition}\n", "Let $A$ be a set of words. The *characteristic function of $A$* is the function \n", "\n", "$$\\chi_A : \\words \\to \\set{\\one,\\hash} $$\n", "\n", "given by \n", "\n", "$$\\chi_A(w) = \\left\\{\n", " \\begin{array}{ll}\n", " \\one & \\mbox{if $w\\in A$} \\\\\n", " \\hash & \\mbox{if $w\\notin A$} \\\\\n", " \\end{array}\n", " \\right.\n", "$$ \n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "ZkwdFYl1iXHH" }, "source": [ "```{prf:definition} \n", "For any set $A$, the *characteristic function of $A$* is the function $\\chi_A$ given by\n", "\n", "$$\n", "\\chi_A(x) = \\left\\{ \\begin{array}{ll} 1 &\\mbox{if $x\\in A$} \\\\ 0 &\\mbox{if $x\\notin A$} \\end{array}\\right.\n", "$$\n", "\n", "A set $A\\subseteq \\words$ is *```1#```-computable* if $\\chi_A$ is a computable function. Other names for \"computable\" include \"decidable\" and \"recursive\".\n", "```\n", "\n", "```{important}\n", "Our work will also involve other notions of \"computable\" besides ```1#```-computability. \n", "We have already seen \n", "*intuitive computability*, and this is not exactly a mathematical concept.\n", "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\". \n", "\n", "The notion which we'll study the most is ```1#``` -computability.\n", "``` " ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "````{prf:proposition}\n", ":label: proposition_finite_computable\n", "\n", "Every finite set of words is a computable set.\n", "````" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "aE3MtTwEk3-a" }, "source": [ "```{exercise}\n", "Let $A$ and $B$ be ```1#```-computable sets. Show that $A\\cap B$, $A\\cup B$, and $\\overline{A}$ are also ```1#```-computable, where \n", "\n", "$$\n", "\\begin{array}{lcl}\n", "A\\cap B & = & \\set{w \\in \\words : w\\in A \\mbox{ and } w\\in B} \\\\\n", "A\\cup B & = & \\set{w \\in \\words : w\\in A \\mbox{ or }\n", " w\\in B \\mbox{ (or both)}} \\\\\n", "\\overline{A} & = & \\set{w\\in \\words : w\\notin A} \\\\\n", "\\end{array}\n", "$$\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "rRwFeOtziM54" }, "source": [ "```{exercise}\n", "Is the set of ```1#``` programs a ```1#```-computable set of words?\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "J4bEhcqH41D-" }, "source": [ "```{exercise}\n", "Show that the following function is ```1#```-computable:\n", "\n", "$$\n", "f(w) = \\left\\{ \n", " \\begin{array}{ll}\n", " w & \\mbox{if every symbol in $w$ is $\\one$}\\\\\n", " \\hash & \\mbox{otherwise}\n", " \\end{array}\n", " \\right.\n", "$$\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "3NawzDg0_aea" }, "source": [ "```{exercise}\n", "\n", "(a)\n", "As a parallel to how we defined ```1#```-computability, define what it means for a function from words to words to be *Python-computable*\n", "\n", "(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.\n", "\n", "[Hint: you will need to say clearly what \"behaves correctly\" means.]\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "VGDZnfsYhjQy" }, "source": [ "# Computable sets and computably enumerable sets\n", "\n", "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.\n", "\n", "```{prf:definition}\n", "Let $p$ be a program. We write $W_p$ for the domain of $\\phifn_p$.\n", "That is, \n", "\n", "$W_p = \\set{x : \\phifn_p(x)\\downarrow}$.\n", "\n", "A set $A\\subseteq\\words$ is *computably enumerable* if there is some program $p$ such that $A = W_p$.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": { "id": "5HP92Numh-Wz" }, "source": [ "```{exercise}\n", "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$.\n", "```" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Equivalence of programs" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "```{admonition} Definition\n", ":class: attention\n", "\n", "Two programs $p$ and $q$ are *equal* if they are identical symbol-by-symbol.\n", "\n", "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.\n", "\n", "The are *equivalent as one-place functions* if $[\\![p]\\!]$ and $[\\![q]\\!]$ are the same partial function.\n", "That is, for all $x$, $[\\![p]\\!](x) \\simeq [\\![q]\\!](x)$.\n", "\n", "More generally, we could define the notion of *equivalent as $n$-place functions* for all natural numbers $n$.\n", "```\n", "\n", "For example, ```1###``` and ```1###1###``` are not equal, but they are strongly equivalent (and thus equivalent as one-place functions).\n", "\n", "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#```.\n", "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.\n", "\n" ] } ], "metadata": { "colab": { "authorship_tag": "ABX9TyM79vNiUG3TjO5WOoOpQBcP", "include_colab_link": true, "provenance": [] }, "kernelspec": { "display_name": "Python 3", "name": "python3" }, "language_info": { "name": "python" } }, "nbformat": 4, "nbformat_minor": 0 }