avewright/proofwiki-math huggingface dataset:
Theorem: Set of Sequence Codes is Primitive Recursive

Let $\operatorname{Seq}$ be the set of all code numbers of finite sequences in $\N$.
Then $\operatorname{Seq}$ is primitive recursive.

Proof:
By the definition of a primitive recursive set, it is sufficient to show that the characteristic function $\chi_{\operatorname{Seq}}$ of $\operatorname{Seq}$ is primitive recursive.
Let $p: \N \to \N$ be the prime enumeration function.
Let $\map {\operatorname{len} } n$ be the length of $n$.
We note that $\map {\chi_{\operatorname{Seq}} } n = 1$ {{iff}} $\map p y$ divides $n$ for $1 \le y \le \map {\operatorname{len} } n$.
That is, {{iff}} $\map {\operatorname{div} } {n, \map p y} = 1$ for $1 \le y \le \map {\operatorname{len} } n$, where $\operatorname{div}$ is the divisor relation.
We then see that $\map {\operatorname{div} } {n, \map p y} = 1$ for $1 \le y \le \map {\operatorname{len} } n$ {{iff}} their product equals $1$.
So we can define $\chi_{\operatorname{Seq}}$ by:
:$\map {\chi_{\operatorname{Seq}} } n = \begin{cases}
\ds \prod_{y \mathop = 1}^{\map {\operatorname{len} } n} \map {\operatorname{div} } {n, \map p y} & : n > 1 \\
0 & : \text{otherwise}
\end{cases}$
Then we define $g: \N^2 \to \N$ as:
:$\map g {n, z} = \begin{cases}
1 & : z = 0 \\
\ds \prod_{y \mathop = 1}^z \map {\operatorname{div} } {n, \map p y} & : z \ne 0
\end{cases}$
We then apply Bounded Product is Primitive Recursive to the primitive recursive function $\map {\operatorname{div} } {n, \map p y}$, and see that $g$ is primitive recursive.
Finally, we have that:
:$\map {\chi_{\operatorname{Seq}} } n = \begin{cases}
\map g {n, \map {\operatorname{len} } n} & : n > 1 \\
0 & : \text{otherwise}
\end{cases}$
is obtained by substitution from:
* the primitive recursive function $\operatorname{len}$
* the primitive recursive function $g$
* the primitive recursive relation $>$
* the constant $1$
So $\chi_{\operatorname{Seq}}$ is primitive recursive.
Hence the result.
{{qed}}
Category:Primitive Recursive Functions
peqmyszs05ygptz6fasgbjky7sitrrs
Theorem: Set of Codes for URM Programs is Primitive Recursive

Let $\operatorname{Prog}$ be the set of all code numbers of URM programs.
Then $\operatorname{Prog}$ is a primitive recursive set.

Proof:
A natural number $n$ codes a URM program {{iff}} it codes a sequence of positive integers which are the code numbers of URM instructions.
Suppose $n$ codes such a sequence.
Then $\map \len n$ is the number of terms in this sequence, where $\map \len n$ is the length of $n$.
Also, for $1 \le j \le \map \len n$, $\paren n_j$ is the exponent of the $j$th prime in the prime decomposition of $n$.
So $\paren n_j$ is the $j$th number in the sequence coded by $n$.
So:
:$n \in \operatorname {Prog}$ {{iff}} $\map {\chi_{\operatorname {Seq} } } n = 1$ and $\paren n_j \in \operatorname{Instr}$ for $1 \le j \le \map \len n$
where $\chi_{\operatorname {Seq} }$ is the characteristic function of the set of code numbers of finite sequences of positive integers.
Now $\paren n_j \in \operatorname{Instr} \iff \map {\chi_{\operatorname {Instr} } } {\paren n_j} = 1$.
So $\paren n_j \in \operatorname{Instr}$ for $1 \le j \le \map \len n$ {{iff}} $\map {\chi_{\operatorname {Instr} } } {\paren n_j} = 1$ for $1 \le j \le \map \len n$.
This is the case {{iff}}:
:$\ds \prod_{j \mathop = 1}^{\map \len n} = 1$
Thus $n \in \operatorname{Prog}$ {{iff}}:
:$\ds \map {\chi_{\operatorname {Seq} } } n \times \prod_{j \mathop = 1}^{\map \len n} = 1$
Now we define the function $g: \N^2 \to \N$ by:
:$\map g {n, z} = \begin{cases}
1 & : z = 0 \\
\ds \prod_{j \mathop = 1}^z \map {\chi_{\operatorname {Instr} } } {\paren n_j} & : \text {otherwise}
\end{cases}$
We use $g$ to obtain the characteristic function of the set $\operatorname {Prog}$:
:$\map {\chi_{\operatorname {Prog} } } n = \map {\chi_{\operatorname {Seq} } } n \map g {n, \map \len n}$
(We need to introduce $g$ to ensure $\chi_{\operatorname{Prog}}$ is defined if $\map \len n = 0$.)
Now we have that:
:$\paren n_j$ is primitive recursive;
:$\operatorname {Instr}$ is primitive recursive.
So $g$ is therefore primitive recursive, as it is obtained by substitution from these.
Therefore $\chi_{\operatorname {Prog}}$ is primitive recursive as it is obtained by substitution from:
:the primitive recursive function $\operatorname {mult}$
:the primitive recursive function $\chi_{\operatorname {Seq} }$
:the primitive recursive function $g$
:the primitive recursive function $\len$.
Hence $\operatorname {Prog}$ is a primitive recursive set.
Category:URM Programs
Category:Primitive Recursive Functions
7y7t7bebgm2gmpjvzmypa26pgo0rtkj
Theorem: Minimization on Relation Equivalent to Minimization on Function

Let $\RR$ be a $k + 1$-ary relation on $\N^{k + 1}$.
Then the function $g: \N^{k + 1} \to \N$ defined as:
:$\map g {n_1, n_2, \ldots, n_k, z} = \mu y \ \map \RR {n_1, n_2, \ldots, n_k, y}$
where $\mu y \ \map \RR {n_1, n_2, \ldots, n_k, y}$ is the minimization operation on $\RR$
is equivalent to minimization on a total function.

Proof:
We have that $\map \RR {n_1, n_2, \ldots, n_k, y}$ holds {{iff}} $\map {\chi_\RR} {n_1, n_2, \ldots, n_k, y} = 1$, from the definition of the characteristic function of a relation.
This in turn holds {{iff}} $\map {\overline \sgn} {\map {\chi_\RR} {n_1, n_2, \ldots, n_k, y} } = 0$, where $\overline \sgn$ is the signum complement function.
Hence we have:
:$\mu y \ \map \RR {n_1, n_2, \ldots, n_k, y} \iff \map {\mu y} {\map {\overline \sgn} {\map {\chi_\RR} {n_1, n_2, \ldots, n_k, y} } = 0}$.
Since $\overline \sgn$ and $\chi_\RR$ are total functions, then so is $\overline \sgn \circ \chi_\RR$.
{{qed}}
Category:Primitive Recursive Functions
Category:Recursive Functions
b6stgrkn4v5ztj0dsgcb27g0uq5ritt
Theorem: Primitive Recursive Function is Total Recursive Function

Every primitive recursive function is a total recursive function.

Proof:
A primitive recursive function is a total function, which is apparent from its method of definition.
As the processes for generate a primitive recursive function are a subset of those to generate a recursive function, it follows that a primitive recursive function is also a recursive function.
The result follows from the definition of a total recursive function.
{{qed}}
Category:Primitive Recursive Functions
Category:Recursive Functions
3nmvtn2sg09j3f6oztavo9f8j59t5vs
Theorem: Function Obtained by Minimization from URM Computable Relations

Let $\RR$ be a URM computable $k+1$-ary relation on $\N^{k + 1}$.
Let the function $f: \N^{k + 1} \to \N$ be a URM computable function.
Let $g: \N^k \to \N$ be the function obtained by minimization from $f$ thus:
:$\map g {n_1, n_2, \ldots, n_k} \approx \mu y \map \RR {n_1, n_2, \ldots, n_k, y}$
Then $g$ is also URM computable.

Proof:
From Minimization on Relation Equivalent to Minimization on Function, minimization on $\RR$ is equivalent to minimization on $\overline \sgn \circ \chi_\RR$.
We have that a Primitive Recursive Function is URM Computable.
By definition, if $\RR$ is URM computable then so is its characteristic function $\chi_\RR$.
We have that Signum Function is Primitive Recursive and thus URM computable.
Thus, from Function Obtained by Substitution from URM Computable Functions, $\overline \sgn \circ \chi_\RR$ is URM computable.
{{qed}}
Category:URM Programs
iy7m7t43n5tjghyu0ap1xob7r3rufcn
Theorem: Recursive Function is URM Computable

Every recursive function is URM computable.

Proof:
From:
* Functions obtained by minimization from URM computable functions are URM computable
* Functions obtained by minimization from URM computable relations are URM computable
* Functions obtained by primitive recursion from URM computable functions are URM computable
* Functions obtained by substitution from URM computable functions are URM computable
* Primitive Recursive Function is URM Computable
* Primitive Recursive Relation is URM Computable
it follows that all the functions obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and minimization (on a function or a relation) are URM computable.
{{qed}}
Category:Recursive Functions
Category:URM Programs
dhr66n2861nap73vuboln1gzoqfyql4
Theorem: Unique Code for State of URM Program

Every state of a URM program can be assigned a unique '''code number'''.
This code number is called the '''state code''' (or '''situation code''').

Proof:
The state of a URM program at a particular point in time is defined as:
:the value of the instruction pointer
:the value, at that point, of each of the registers that are used by the program.
Let $P$ be a URM program.
Suppose that, at a given stage of computation:
:the value of the instruction pointer is $a$;
:the value of register $R_k$ is $r_k$.
Let $b = \map \rho P$ be the number of registers used by $P$.
Then we can define the '''state code''' $s$ as:
:$s = p_1^a p_2^{r_1} p_3^{r_2} \cdots p_{b + 1}^{r_b}$
where $p_j = \map p j$ is defined as the $j$th prime number.
Hence it follows from the Fundamental Theorem of Arithmetic that $s$ is uniquely specified for any given state.
{{qed}}
Theorem: URM Computable Function is Recursive

Every URM computable function is recursive.

Proof:
Let $f: \N^k \to \N$ be a URM computable function.
Then by hypothesis there is a URM program that computes $f$.
Let $P$ be the URM program with the smallest code number that computes $f$.
Let $e = \map \gamma P$ be the code number of $P$.
Consider the function $g: \N^k \to \N$ given by:
:$\map g {n_1, n_2, \ldots, n_k} \approx \map {\mu t} {\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e}$
where:
:$\map \len e$ is the length of $e$
:$\mu t$ is the minimization operation on $S_k$
:$\approx$ denotes partial function equality
:$\map {S_k} {e, n_1, n_2, \ldots, n_k, t}$ is the state code at stage $t$ of the computation of $P$ with input $\tuple {n_1, n_2, \ldots, n_k}$
:the number $\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1$ is the code number of the instruction about to be carried out at stage $t$.
So the inequality:
:$\tuple {\map {S_k} {e, n_1, n_2, \ldots, n_k, t} }_1 > \map \len e$
expresses the fact that at stage $t$ the computation has halted.
So the value of $\map g {n_1, n_2, \ldots, n_k}$ is the state code of the first stage at which computation has halted, if there is one, and undefined otherwise.
Since the functions in this inequality, and the sign $>$ itself, are all primitive recursive, it follows that the inequality expresses a primitive recursive relation on $e, n_1, n_2, \ldots, n_k, t$.
Thus $g$ is a recursive function by definition, as it can be obtained by minimization on a recursive relation.
Now consider the function $h: \N^k \to \N$ given by:
:$\map h {n_1, n_2, \ldots, n_k} \approx \map {S_k} {e, n_1, n_2, \ldots, n_k, \map g {n_1, n_2, \ldots, n_k} }$
This is recursive because it was obtained by substitution from known recursive functions.
Now $\map h {n_1, n_2, \ldots, n_k}$ is defined iff the computation halts, and it gives the value of the state code when it has halted.
The output of this computation, which gives the value of $f$, is the number in register $R_1$.
But the number in $R_1$ is the exponent of $p_2 = 3$ in the expression of the state code $\map h {n_1, n_2, \ldots, n_k}$ in the form $p_1^a p_2^{r_1} p_3^{r_2} \cdots p_{k + 1}^{r_k}$.
Thus the function $f$ is given by:
:$\map f {n_1, n_2, \ldots, n_k} \approx \tuple {\map h {n_1, n_2, \ldots, n_k} }_2$.
It follows that $f$ is a recursive function, since it is obtained by substitution from known recursive functions.
{{qed}}
Theorem: Kleene's Normal Form Theorem

For each integer $k \ge 1$, there exists:
:a primitive recursive $k + 1$-ary relation $T_k$
:a primitive recursive function $U: \N \to \N$
such that a partial function $f: \N^k \to \N$ is recursive {{iff}}, for some $e \in \N$ and all $\tuple {n_1, n_2, \ldots, n_k} \in \N^k$:
:$\map f {n_1, n_2, \ldots, n_k} \approx \map U {\mu z \ \map {T_k} {e, n_1, n_2, \ldots, n_k, z} }$

Proof:
See the proof of URM Computable Function is Recursive for an explanation of the symbols used here.
Theorem: Recursive Function uses One Minimization

Every recursive function can be obtained from the basic primitive recursive functions using:
* substitution
* primitive recursion
* at most one minimization on a function.

Proof:
Let $f: \N^k \to \N$ be any recursive function.
Consider the minimization operation on the $k + 2$-ary relation $\map \RR {n_1, n_2, \ldots, n_k, y}$:
:$\mu y \mathrel \RR \tuple {n_1, n_2, \ldots, n_k, y}$
From Minimization on Relation Equivalent to Minimization on Function, this is equivalent to:
:$\map {\mu y} {\map {\overline \sgn} {\map {\chi_\RR} {n_1, n_2, \ldots, n_k, y} } = 0}$.
So we can rewrite the statement of Kleene's Normal Form Theorem as:
:$(1) \quad \map f {n_1, n_2, \ldots, n_k} \approx \map U {\map {\mu z} {\map {\overline \sgn} {\map {\chi_\RR} {e, n_1, n_2, \ldots, n_k, z} } = 0} }$.
From the proof of that theorem, we have that $T_k$ is primitive recursive.
Hence from the definition of characteristic function, so is $\chi_{T_k}$.
{{explain|What is $T_k$?}}
We also know that Signum Function is Primitive Recursive.
We also have {{hypothesis}} that $U$ is primitive recursive.
Hence all of $\chi_{T_k}$, $\overline \sgn$ and $U$ can be defined without using minimization.
So the only minimization involved in obtaining the values of $f$ in $(1)$ is the one explicitly mentioned in $(1)$.
Hence the result.
{{qed}}
Category:Recursive Functions
hsex9vkwl3ka0a9r02ao3djombo0tkc
Theorem: Universal URM Computable Functions

For each integer $k \ge 1$, there exists a URM computable function:
:$\Phi_k: \N^{k+1} \to \N$
such that for each URM computable function $f: \N^k \to \N$ there exists a natural number $e$ such that:
:$\forall \left({n_1, n_2, \ldots, n_k}\right) \in \N^k: f \left({n_1, n_2, \ldots, n_k}\right) \approx \Phi_k \left({e, n_1, n_2, \ldots, n_k}\right)$.
This function $\Phi_k$ is '''universal for URM computable functions of $k$ variables'''.

Proof:
Let $\Phi_k: \N^{k+1} \to \N$ be given by:
:$\Phi_k \left({e, n_1, n_2, \ldots, n_k}\right) = U \left({\mu z \ T_k \left({e, n_1, n_2, \ldots, n_k, z}\right)}\right)$
where $T_k$ and $U$ are as in Kleene's Normal Form Theorem.
Thus we have reinterpreted Kleene's Normal Form Theorem as being about URM computable functions.
This is legitimate, as a URM Computable Function is Recursive and vice versa.
{{qed}}
Theorem: Universal URM Programs

For each integer $k \ge 1$, there exists a URM program $P_k$ such that:
For each URM program $P$ there exists a natural number $e$ such that:
For all $\left({n_1, n_2, \ldots, n_k}\right) \in \N^k$, the computation using the program $P_k$ with input $\left({e, n_1, n_2, \ldots, n_k}\right)$
has the same output as the computation using the program $P$ with input $\left({n_1, n_2, \ldots, n_k}\right)$.
This function $P_k$ is a '''universal program for URM computations with $k$ inputs'''.

Proof:
This follows directly from:
* Kleene's Normal Form Theorem;
* Universal URM Computable Functions.
{{qed}}
Category:URM Programs
557hxwrpy6pu9y2am1yzmuwcl59xj3w
Theorem: Combination of Recursive Functions

Let $f: \N^k \to \N$ and $g: \N^k \to \N$ be recursive functions (not necessarily total), where $k \ge 1$.
Let $\RR$ be a $k$-ary relation such that:
:if $\map \RR {n_1, n_2, \ldots, n_k}$ holds, then $\map f {n_1, n_2, \ldots, n_k}$ is defined
:if $\map \RR {n_1, n_2, \ldots, n_k}$ does not hold, then $\map g {n_1, n_2, \ldots, n_k}$ is defined.
Let $h: \N^k \to \N$ be the function defined as:
:$\map h {n_1, n_2, \ldots, n_k} = \begin {cases}
\map f {n_1, n_2, \ldots, n_k} & : \text{if } \map \RR {n_1, n_2, \ldots, n_k} \text { holds} \\
\map g {n_1, n_2, \ldots, n_k} & : \text{otherwise}
\end {cases}$
so that $h$ is total.
Then $h$ is recursive.
{{handwaving|It seems to me that we need to assume something about $\RR$ to make it computable which of the two cases holds at any given tuple}}

Proof:
Let $P_f, P_g, P_\RR$ be the URM programs computing, respectively, the functions $f$ and $g$ and the characteristic function $\chi_\RR$.
From Recursive Function is URM Computable, these programs are guaranteed to exist.
An informal algorithm for computing $h$ is as follows.
# Input $\tuple {n_1, n_2, \ldots, n_k}$.
# Use $P_\RR$ to determine whether $\map \RR {n_1, n_2, \ldots, n_k}$ holds.
# If it holds, use $P_f$ to compute $\map f {n_1, n_2, \ldots, n_k}$.
# If it does not hold, use $P_g$ to compute $\map g {n_1, n_2, \ldots, n_k}$.
The result follows from URM Computable Function is Recursive.
{{qed}}
Theorem: Not All URM Computable Functions are Primitive Recursive

There exist URM computable functions which are not primitive recursive.

Proof:
Consider the basic primitive recursive functions.
To each basic primitive recursive function $f$ let us assign a code number $\map \delta f$, as follows:
* $\map \delta {\operatorname{zero} } = 3$
* $\map \delta {\operatorname{succ} } = 9$
* $\forall k, m \in \N^*: m \le k: \map \delta {\pr^k_m} = 2^k 3^m$
Suppose the function $h$ is defined by substitution from the functions $f, g_1, g_2, \ldots, g_t$ to which we have already assigned code numbers.
Then we put:
:$\map \delta h = 2^{\map \delta f} 3^{\map \delta {g_1} } 5^{\map \delta {g_2} } \cdots  p_{t + 1}^{\map \delta {g_t} } + 1$
Suppose the function $h$ is defined by primitive recursion from the functions $f$ and $g$ to which we have already assigned code numbers.
Then we put:
:$\map \delta h = 2^{\map \delta f} 3^{\map \delta g} + 2$
Thus we assign a '''code number''' to every definition of a primitive recursive function.
Given any natural number $m$ we can determine whether $m$ is the code number for a definition of a primitive recursive function, and if so, work out what definition it encodes.
In particular, given any such $m$ we can work out whether it encodes a primitive recursive function $f: \N \to \N$, and determine how $f$ is built up from basic primitive recursive functions on up.
From this definition, we can compute all the values of $f$ for all inputs $n \in \N$.
So, we define the function $\Phi: \N^2 \to \N$ as follows:
:$\map \Phi {m, n} = \begin{cases}
\map f n & : \text{if } m \text { codes a definition of the primitive recursive function } f: \N \to \N \\
0 & : \text{otherwise}
\end{cases}$
It is deducible by arguments derived from proofs of the various primitive recursive functions that there is a URM program for computing the values of $\Phi$.
That is, $\Phi$ can be shown to be URM computable
Now we apply Cantor's Diagonal Argument to create the following URM computable function $g: \N \to \N$:
:$\map g n = \map \Phi {n, n} + 1$
We have that $\Phi$ is URM computable.
So it follows that $\map g n$ is also URM computable.
Now, let $f$ be a primitive recursive function and let $m$ code some definition of $f$.
So, for all $n \in \N$, we have:
:$\map f n = \map \Phi {m, n}$
Thus $\map f m = \map \Phi {m, m}$.
Now, since $\map g m = \map \Phi {m, m} + 1$, we see that $\map g m \ne \map f m$, whatever $f$ may happen to be.
Hence $g \ne f$.
So $g$ is different from any primitive recursive function $f$ that we care to devise.
Therefore $g$ is a URM computable function which is not primitive recursive.
Hence the result.
{{qed}}
Category:URM Programs
Category:Primitive Recursive Functions
sqvgrim92s2i9ve8qrk7gtndfwkhmga
Theorem: Cantor's Diagonal Argument

Let $S$ be a set such that $\card S > 1$, that is, such that $S$ is not a singleton.
Let $\mathbb F$ be the set of all mappings from the natural numbers $\N$ to $S$:
:$\mathbb F = \set {f: \N \to S}$
Then $\mathbb F$ is uncountably infinite.

Proof:
First we note that as $\card S > 1$, there are at least two elements of $S$ which are distinct.
Call these distinct elements $a$ and $b$.
That is:
:$\exists a, b \in S: a \ne b$
First we show that $\mathbb F$ is infinite, as follows.
For each $m \in \N$, let $\phi_m$ be the mapping defined as:
:<nowiki>$\map {\phi_m} n = \begin{cases}
a & : n \ne m \\
b & : n = m
\end{cases}$</nowiki>
Then:
:$\forall m_1, m_2 \in \N: m_1 \ne m_2 \implies \phi_{m_1} \ne \phi_{m_2}$
as:
:$b = \map {\phi_{m_1} } {m_1} \ne \map {\phi_{m_2} } {m_1} = a$
So the mapping $\Psi: \N \to \mathbb F$ defined as:
:$\map \Psi n = \phi_n$
is an injection.
Thus $\mathbb F$ is infinite from Infinite if Injection from Natural Numbers.
Next we show that $\mathbb F$ is uncountable.
Let $\Phi: \N \to \mathbb F$ be a mapping.
For each $n \in \N$ let $f_n: \N \to S$ be the function $\map \Phi n$.
Let us define $g: \N \to \N$ by:
:<nowiki>$\map g n = \begin{cases}
a & : \map {f_n} n \ne a \\
b & : \map {f_n} n = a
\end{cases}$</nowiki>
Then $g \in \mathbb F$, but:
:$\forall n \in \N: \map g n \ne \map {f_n} n$
and so $g \ne f_n$.
Since $g$ is an element of $\mathbb F$ which is different from all the values taken by $\Phi$, it follows that $\Phi$ is not a surjection and hence not a bijection.
Thus no bijection exists between $\mathbb F$ and $\N$.
By definition of countably infinite, $\mathbb F$ is countably infinite {{iff}} there is a bijection between $\mathbb F$ and $\N$.
Therefore $\mathbb F$ is uncountable.
{{qed}}
Theorem: Infinite if Injection from Natural Numbers

Let $S$ be a set.
Let there exist an injection $\phi: \N \to S$ from the natural numbers to $S$.
Then $S$ is infinite.

Proof:
{{AimForCont}} that $S$ is finite.
Let $k \in \N$ be such that there exists a bijection $\psi: S \to \N_k$.
Note that $\N_k \subset \N$ since $k \in \N$, $k \notin \N_k$.
Consider the restriction $\phi \restriction \N_k$ of $\phi$ to $\N_k$.
Then $\phi \restriction \N_k: \N_k \to S$ is an injection by Restriction of Injection is Injection.
From Equivalence of Mappings between Finite Sets of Same Cardinality, it is also a bijection.
Consider $\map \phi k \in S$.
As $\phi \restriction \N_k$ is a surjection, there exists a $j \in \N_k$ such that:
:$\map \phi j = \map {\phi \restriction \N_K} j = \map \phi k$
Since $j \ne k$, it follows that $\phi$ cannot be an injection.
So there can be no such $k$.
Hence $S$ is infinite.
{{qed}}
Category:Injections
Category:Infinite Sets
hwye0cy7g2z0boopp11aqd1t0fkm5cx
Theorem: Halting Problem is Not Algorithmically Decidable

Let $H: \N^2 \to \N$ be the function given by:
:$\map H {m, n} = 1$ if $m$ codes a URM program which halts with input $n$
:$\map H {m, n} = 0$ otherwise.
Then $H$ is not recursive.

Proof:
We perform a proof by Cantor's Diagonal Argument.
{{AimForCont}} $H$ is recursive.
Consider the universal URM computable function $\Phi_1: \N^2 \to \N$.
Let $f: \N \to \N$ be the function given by:
:$\map f n = \begin{cases}
\map {\Phi_1} {n, n} & : \map H {n, n} = 1 \\
0 & : \text{otherwise}
\end{cases}$
As $H$ is recursive, the relation $\map H {n, n} = 1$ is also recursive.
The universal function is recursive as all URM computable functions are recursive.
Also, $\map {\Phi_1} {n, n}$ is defined when $\map H {n, n} = 1$.
The constant $0$ is (primitive) recursive and always defined.
So $f$ is total, and by Combination of Recursive Functions it is also recursive.
It follows immediately that the function $g: \N \to \N$ given by:
:$\map g n = \map f n + 1$
is also recursive.
So by Universal URM Computable Functions there exists some $e \in \N$ such that:
:$\forall n: \map g n = \map {\Phi_1} {e, n}$
that is, the URM program coded by $e$ computes $g$.
Hence:
:$\map g e = \map {\Phi_1} {e, e}$
But since $e$ codes a URM program which halts with input $e$, we have:
:$\map H {e, e} = 1$
and so:
:$\map f e = \map {\Phi_1} {e, e}$
Therefore, by definition of $g$, we have:
:$\map g e = \map {\Phi_1} {e, e} + 1$
This contradiction arose because we assumed that $H$ is recursive.
Hence the result.
{{Qed}}
Category:URM Programs
Category:Recursion Theory
slcqir8a3zos2uy9urpudguejs10i7l