nyuuzyou/wikis huggingface dataset:
Recurrence Relation for Bell Numbers/Illustration

== Illustration of Recurrence Relation for Bell Numbers ==
We have:
:$B_{n + 1} = \ds \sum_{k \mathop = 0}^n \dbinom n k B_k$
Let $n = 3$.
Then: 
Let $S = \set {a, b, c, d}$.
The $1$ in $(1)$ represents all of the elements combined ($B_0 = 1$):
:$\set {a, b, c, d}$
The $3$ in $(1)$ represents the sets where element $d$ is part of a triplet ($3 B_1 = 3$):
:$\set {\set a \set {b, c, d} }$
:$\set {\set b \set {a, c, d} }$
:$\set {\set c \set {a, b, d} }$
The $6$ in $(1)$ represents the sets where element $d$ is part of a couple ($3 B_2 = 6$):
:$\set {\set {a, d} \set {b, c} }$
:$\set {\set {a, d} \set b \set c}$
:$\set {\set {b, d} \set {a, c} }$
:$\set {\set {b, d} \set a \set c}$
:$\set {\set {c, d} \set {a, b} }$
:$\set {\set {c, d} \set a \set b}$
Finally, the $5$ in $(1)$ represents where element $d$ is by itself and the remaining $3$ elements are partitioned ($B_3 = 5$):
:$\set {\set d, \set {a, b, c} }$
:$\set {\set d, \set a, \set {b, c} }$
:$\set {\set d, \set b, \set {a, c} }$
:$\set {\set d, \set c, \set {a, b} }$
:$\set {\set d, \set a, \set b, \set c}$
Category:Recurrence Relation for Bell Numbers
Recurrence Relation for Digamma Function

== Theorem ==
:$\map \psi {z + 1} = \map \psi z + \dfrac 1 z$
where:
:$\psi$ denotes the digamma function
:$z \in \C \setminus \Z_{\le 0}$.
== Proof ==
== Also see ==
* Recurrence Relation for General Harmonic Numbers
* Recurrence Relation for Polygamma Function
== Sources == 
* 
Category:Digamma Function
Category:Recurrence Relations
Recurrence Relation for Euler Numbers

== Theorem ==
Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Then:
where $E_n$ denotes the $n$th Euler number.
== Proof ==
== Also presented as ==
== Examples ==
== Also see ==
* Sum of Euler Numbers by Binomial Coefficients Vanishes
== Sources ==
* : $\S 21$: Relationships of Bernoulli and Euler Numbers: $21.6$
* : $\S 23$: Bernoulli and Euler Numbers: Relationships of Bernoulli and Euler Numbers: $23.6.$
Category:Recurrence Relation for Euler Numbers
Category:Euler Numbers
Category:Recurrence Relations
Recurrence Relation for Euler Numbers/Also presented as

== Recurrence Relation for Euler Numbers: Also presented as == 
Recurrence Relation for Euler Numbers can also be presented using the alternative form of the Euler numbers:
== Sources ==
* : $\S 21$: Relationships of Bernoulli and Euler Numbers: $21.6$
* : $\S 23$: Bernoulli and Euler Numbers: Relationships of Bernoulli and Euler Numbers: $23.6.$
Category:Recurrence Relation for Euler Numbers
Recurrence Relation for Fibonomial Coefficients

== Theorem ==
:$\dbinom n k_\FF = F_{k - 1} \dbinom {n - 1} k_\FF + F_{n - k + 1} \dbinom {n - 1} {k - 1}_\FF$
where:
:$\dbinom n k_\FF$ denotes a Fibonomial coefficient
:$F_{k - 1}$ etc. denote Fibonacci numbers.
== Proof ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $29 \ \text{(b)}$
Category:Fibonomial Coefficients
Recurrence Relation for General Harmonic Numbers

== Theorem ==
:$\harm r x = \harm r {x - 1} + \dfrac 1 {x^r}$
where:
:$\harm r x$ denotes the general harmonic number of order $r$ evaluated at $x$.
== Proof ==
== Also see ==
* Recurrence Relation for Digamma Function
* Recurrence Relation for Polygamma Function
Category:General Harmonic Numbers
Category:Recurrence Relations
Recurrence Relation for Number of Derangements on Finite Set

== Theorem ==
The number of derangements $D_n$ on a finite set $S$ of cardinality $n$ is:
:$D_n = \paren {n - 1} \paren {D_{n - 1} + D_{n - 2} }$
where $D_1 = 0$, $D_2 = 1$.
== Proof ==
Let $\card S = 1$ such that $S = \set s$, say.
Then $\map f s = s$ is the only permutation on $S$.
This by definition is not a derangement.
Thus:
:$D_1 = 0$
Let $\card S = 2$.
Then $S = \set {s, t}$, say.
There are two permutations on $S$:
:$f = \set {\tuple {s, s}, \tuple {t, t} }$
and:
:$g = \set {\tuple {s, t}, \tuple {t, s} }$
and only the latter is a derangement.
So:
:$D_2 = 1$
Let $\card S > 2$.
Let $f: S \to S$ be a derangement.
We aim to count the total number of such $f$. 
, we can take:
:$S = \set {1, 2, \ldots, n + 1}$
Now, consider an arbitrary $s \in S$ such that $s \ne 1$.
Let $\map f s = 1$.
By the Sum Rule for Counting, the total number of $f$ will be: 
:$\paren {\text {the number of $f$ where } \map f 1 \ne s} + \paren {\text {the number of $f$ where} \map f 1 = s}$
=== Case 1 ===
:$\map f 1 \ne s$
Take:
:$T_1 = \set {1, 2, \dotsc, s - 1, s + 1, \dotsc, n + 1} = S \setminus \set s$
Define the derangement $g_1: T_1 \to T_1$ by:
:$\forall t \in T_1: \map {g_1} t = \map f t$
Then $g_1$ is a derangement on a set of cardinality $n$.
Thus there are $D_n$ such $g_1$. 
Note that:
:$f = g_1 \cup \map f s$
We have that $s$ can be chosen in $n$ ways.
By the Product Rule for Counting there are in total $n D_n$ such $f$ where $\map f s \ne 1$.
=== Case 2 ===
:$\map f 1 = s$
Take:
:$T_2 = \set {2, 3, \dotsc, s - 1, s + 1, \dotsc, n + 1} = S \setminus \set {1, s}$
Define the derangement $g_2: T_2 \to T_2$ by:
:$\forall t \in T_2: \map {g_2} t = \map f t$
Then $g_2$ is a derangement on a set of cardinality $n - 1$.
So there are $D_{n - 1}$ such $g_2$. 
Note that:
:$f = g_2 \cup \set s \cup \map f s$
We have that $s$ can be chosen in $n$ ways
By the Product Rule for Counting there are in total $n D_{n - 1}$ such $f$ where $\map f s = 1$.
Summing the results from both cases, we get the total number of derangements $f$ on a set of cardinality $n + 1$ is:
:$D_{n + 1} = n D_n + n D_{n - 1} = n \paren {D_n + D_{n - 1} }$
as was to be proved.
== Sources ==
* 
Category:Number of Derangements on Finite Set
Category:Derangements
Category:Counting Arguments
Recurrence Relation for Polygamma Function

== Theorem ==
:$\map {\psi_n} {z + 1} = \map {\psi_n} z + \paren {-1}^n n! z^{-n - 1}$
where:
:$\psi_n$ denote the $n$th polygamma function
:$z \in \C \setminus \Z_{\le 0}$.
== Proof 1 ==
== Proof 2 ==
== Also presented as ==
== Also see ==
* Recurrence Relation for Digamma Function
* Recurrence Relation for General Harmonic Numbers
== Sources == 
* 
Category:Recurrence Relation for Polygamma Function
Category:Polygamma Function
Category:Recurrence Relations
Recurrence Relation for Polygamma Function/Also presented as

== Recurrence Relation for Polygamma Function: Also presented as ==
The Recurrence Relation for Polygamma Function can also be presented as:
:$\map {\psi_n} {z + 1} = \map {\psi_n} z + \dfrac {\paren {-1}^n n!} {z^{n + 1} }$
Category:Recurrence Relation for Polygamma Function
Recurrence Relation for Polygamma Function/Proof 1

== Theorem ==
== Proof ==
By definition:
:$\map {\psi_n} z = \dfrac {\d^n} {\d z^n} \map \psi z$
where:
:$\psi$ denotes the digamma function
:$z \in \C \setminus \Z_{\le 0}$.
Then:
Category:Recurrence Relation for Polygamma Function
Recurrence Relation for Polylogarithms

== Theorem ==
:$\ds \map {\Li_{s + 1} } z = \int_0^z \dfrac {\map {\Li_s} t} t \rd t$
where:
:$\map {\Li_s} z$ denotes the polylogarithm.
== Proof ==
Category:Polylogarithm
Category:Recurrence Relations
Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers

== Theorem ==
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Then:
:$\ds \sum_{k \mathop \in \Z} \dbinom m k_\FF \paren {-1}^{\ceiling {\paren {m - k} / 2} } {F_{n + k} }^{m - 1} = 0$
where:
:$\dbinom m k_\FF$ denotes a Fibonomial coefficient
:$F_{n + k}$ denotes the $n + k$th Fibonacci number
:$\ceiling {\, \cdot \,}$ denotes the ceiling function
== Proof ==
=== Lemma 1 ===
=== Lemma 2 ===
== Examples ==
== Historical Note ==
== Sources ==
* 
* 
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $30$
Category:Fibonomial Coefficients
Category:Fibonacci Numbers
Category:Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers
Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers/Examples/m = 3

== Example of Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers ==
:${F_n}^n - 2 {F_{n + 1} }^2 - 2 {F_{n + 2} }^2 + {F_{n + 3} }^2 = 0$
== Proof ==
Set $m = 3$ into Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers:
:$\ds \sum_{k \mathop \in \Z} \dbinom m k_\FF \paren {-1}^{\ceiling {\paren {m - k} / 2} } {F_{n + k} }^{m - 1} = 0$
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $30$
Category:Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers
Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers/Lemma 1

== Theorem ==
:$\ds \sum_{k \mathop \in \Z} \dbinom m k_\FF \paren {-1}^{\ceiling {\paren {m - k} / 2} } {F_{n + k} }^{m - 2} F_k = F_m \sum_{k \mathop \in \Z} \dbinom {m - 1} {k - 1}_\FF \paren {-1}^{\ceiling {\paren {m - k} / 2} } {F_{n + k} }^{m - 2} = 0$
where:
:$\dbinom m k_\FF$ denotes a Fibonomial coefficient
:$F_{n + k}$ denotes the $n + k$th Fibonacci number
:$\ceiling {\, \cdot \,}$ denotes the ceiling function
== Proof ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $30$: Solution: $\text{(a)}$
Category:Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers
Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers/Lemma 2

== Theorem ==
:$\ds \sum_{k \mathop \in \Z} \dbinom m k_\FF \paren {-1}^{\ceiling {\paren {m - k} / 2} } {F_{n + k} }^{m - 2} \paren {-1}^k F_{m - k} = \paren {-1}^m F_m \sum_{k \mathop \in \Z} \dbinom {m - 1} k_\FF \paren {-1}^{\ceiling {\paren {m - 1 - k} / 2} } {F_{n + k} }^{m - 2} = 0$
where:
:$\dbinom m k_\FF$ denotes a Fibonomial coefficient
:$F_{n + k}$ denotes the $n + k$th Fibonacci number
:$\ceiling {\, \cdot \,}$ denotes the ceiling function
== Proof ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $30$: Solution: $\text{(b)}$
Category:Recurrence Relation for Sequence of mth Powers of Fibonacci Numbers
Recurrence Relation where n+1th Term is A by nth term + B to the n

== Theorem ==
Let $\sequence {a_n}$ be the sequence defined by the recurrence relation:
:$a_n = \begin {cases} 0 & : n = 0 \\ A a_{n - 1} + B^{n - 1} & : n > 0 \end {cases}$
for numbers $A$ and $B$.
Then the closed form for $\sequence {a_n}$ is given by:
:$a_n = \begin {cases} \dfrac {A^n - B^n} {A - B} & : A \ne B \\ n A^{n - 1} & : A = B \end {cases}$
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$a_n = \begin {cases} \dfrac {A^n - B^n} {A - B} & : A \ne B \\ n A^{n - 1} & : A = B \end {cases}$
$\map P 0$ is the case:
When $A = B$:
Thus $\map P 0$ is seen to hold.
=== Basis for the Induction ===
$\map P 1$ is the case:
When $A = B$:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
This is the induction hypothesis:
:$a_k = \begin {cases} \dfrac {A^k - B^k} {A - B} & : A \ne B \\ k A^{k - 1} & : A = B \end {cases}$
from which it is to be shown that:
:$a_{k + 1} = \begin {cases} \dfrac {A^{k + 1} - B^{k + 1} } {A - B} & : A \ne B \\ \paren {k + 1} A^k & : A = B \end {cases}$
=== Induction Step ===
This is the induction step:
First let $A \ne B$.
When $A = B$ we have for $k > 0$:
So $\map P k \implies \map P {k + 1}$ and by the Principle of Mathematical Induction:
:$a_n = \begin {cases} \dfrac {A^n - B^n} {A - B} & : A \ne B \\ n A^{n - 1} & : A = B \end {cases}$
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $28$ (solution)
Category:Closed Forms
Recurring Parts of Multiples of One Thirteenth

== Theorem ==
The multiples of $\dfrac 1 {13}$ from $\dfrac 1 {13}$ to $\dfrac {12} {13}$ can be divided into two sets of equal size:
:one where the digits of the recurring part consists of a cyclic permutation of $076923$
:one where the digits of the recurring part consists of a cyclic permutation of $153846$.
:
== Proof ==
== Also see ==
* Reciprocal of 13
== Sources ==
* : $13$
* : $076,923$
* : $13$
* : $076,923$
Category:Number Theory
Category:13
Category:One Thirteenth
Category:Examples of Reciprocals
Recurring Parts of Multiples of Reciprocal of 53

== Theorem ==
The multiples of $\dfrac 1 {53}$ from $\dfrac 1 {53}$ to $\dfrac {52} {53}$ can be divided into $4$ sets of equal size:
:one where the digits of the recurring part consists of a cyclic permutation of $01886 \, 79245 \, 283$
:one where the digits of the recurring part consists of a cyclic permutation of $03773 \, 58490 \, 566$
:one where the digits of the recurring part consists of a cyclic permutation of $07547 \, 16981 \, 132$
:one where the digits of the recurring part consists of a cyclic permutation of $09433 \, 96226 \, 415$.
== Proof ==
== Sources ==
* : $53$
* : $53$
Category:Number Theory
Category:53
Recursion Property of Elementary Symmetric Function

== Theorem ==
Let $\set {z_1, z_2, \ldots, z_{n + 1} }$ be a set of $n + 1$ numbers, duplicate values permitted.
Then for $1 \le m \le n$:
:$\map {e_m} {\set {z_1, \ldots, z_n, z_{n + 1} } } = z_{n + 1} \map {e_{m - 1} } {\set {z_1, \ldots, z_n} } + \map {e_m} {\set {z_1, \ldots, z_n} }$
where $\map {e_m} {\set {z_1, \ldots, z_n} }$ denotes the elementary symmetric function of degree $m$ on $\set {z_1, \ldots, z_n}$.
== Proof 1 ==
== Proof 2 ==
== Examples ==
Category:Recursion Property of Elementary Symmetric Function
Category:Elementary Symmetric Functions
Recursion Property of Elementary Symmetric Function/Examples

== Examples of Use of Recursion Property of Elementary Symmetric Function==
=== Example: $x_{n + 1} \map {e_n} {\set {x_1, x_2, \ldots, x_n} } = \map {e_{n + 1} } {\set {x_1, x_2, \ldots, x_n, x_{n + 1} } }$ ===
Category:Recursion Property of Elementary Symmetric Function
Recursion Property of Elementary Symmetric Function/Examples/Product of n+1 Factors

== Examples of Use of Recursion Property of Elementary Symmetric Function==
Let $\set {z_1, z_2, \ldots, z_{n + 1} }$ be a set of $n + 1$ numbers, duplicate values permitted.
Then:
:$x_{n + 1} \map {e_n} {\set {x_1, x_2, \ldots, x_n} } = \map {e_{n + 1} } {\set {x_1, x_2, \ldots, x_n, x_{n + 1} } }$
where $\map {e_n} {\set {x_1, x_2, \ldots, x_n} }$ denotes the elementary symmetric function of degree $n$ on $\set {z_1, \ldots, z_n}$.
== Proof ==
Category:Recursion Property of Elementary Symmetric Function
Recursion Property of Elementary Symmetric Function/Proof 1

== Theorem ==
== Proof ==
Case $m = 1$ holds because $e_0$ is $1$ and $e_1$ is the sum of the elements.
Assume $2 \le m \le n$.
Define four sets:
:$A = \set {\set {p_1, \ldots, p_m} : 1 \le p_1 < \cdots < p_m \le n + 1}$
:$B = \set {\set {p_1, \ldots, p_m} : 1 \le p_1 < \cdots < p_{m - 1} \le n, p_m = n + 1}$
:$C = \set {\set {p_1, \ldots, p_m} : 1 \le p_1 < \cdots < p_m \le n}$
:$D = \set {\set {p_1, \ldots, p_{m - 1} } : 1 \le p_1 < \cdots < p_{m - 1} \le n}$
Then $A = B \cup C$ and $B \cap C = \O$ implies:
:$\ds \sum_A z_{p_1} \cdots z_{p_m} = \sum_B z_{p_1} \cdots z_{p_m} + \sum_C z_{p_1} \cdots z_{p_m}$
Simplify:
:$\ds \sum_B z_{p_1} \cdots z_{p_m} = z_{n + 1} \sum_D z_{p_1} \cdots z_{p_{m - 1} }$
By definition of elementary symmetric function:
Assemble the preceding equations:
Category:Recursion Property of Elementary Symmetric Function
Recursion Property of Elementary Symmetric Function/Proof 2

== Theorem ==
== Proof ==
Recall the definition of elementary symmetric function:
Consider the summands of $\map {e_m} {\set {z_1, z_2, \ldots, z_n, z_{n + 1} } }$:
:$z_{j_1} z_{j_2} \cdots z_{j_m}$
where $1 \le j_1 < j_2 < \cdots j_m \le n + 1$.
They consist of $2$ types:
:Type $(1)$: such that $j_m < n + 1$
:Type $(2)$: such that $j_m = n + 1$.
We have that:
:the summands of Type $(1)$ are exactly the summands of $\map {e_m} {\set {z_1, z_2, \ldots, z_n} }$
:the summands of Type $(2)$ consist of the summands of $\map {e_{m - 1} } {\set {z_1, z_2, \ldots, z_n} }$ multiplied by $z_{n + 1}$.
Hence the result.
Category:Recursion Property of Elementary Symmetric Function
Recursive Construction of Transitive Closure

== Theorem ==
Let $\RR$ be a relation.
The transitive closure $\RR^+$ of $\RR$ can be constructed as follows:
Let:
:$\RR_n := \begin {cases} \RR & : n = 0 \\ \RR_{n - 1} \cup \set {\tuple {x_1, x_3}: \exists x_2: \tuple {x_1, x_2} \in \RR_{n-1} \land \tuple {x_2, x_3} \in \RR_{n - 1} } & : n > 0 \end{cases}$
Finally, let:
:$\ds \RR^+ = \bigcup_{i \mathop \in \N} \RR_i$
Then $R^+$ is the transitive closure of $R$.
== Proof ==
We must show that:
:$(1): \quad \RR \subseteq \RR^+$
:$(2): \quad \RR^+$ is transitive
:$(3): \quad \RR^+$ is the smallest relation with both of those characteristics.
=== Proof of Subset ===
$\RR \subseteq \RR^+$: $\RR^+$ contains all of the $\RR_i$, so in particular $\RR^+$ contains $\RR$.
=== Proof of Transitivity ===
Every element of $\RR^+$ is in one of the $\RR_i$.
From the method of construction of $\RR^+$:
:$\forall i, j \in \N: \RR_i \subseteq \RR_{\max \set {i, j} }$
Suppose $\tuple {s_1, s_2} \in \RR_j$ and $\tuple {s_2, s_3} \in \RR_k$.
Then as:
:$\RR_j \subseteq \RR_{\max \set {j, k} }$
and:
:$\RR_k \subseteq \RR_{\max \set {j, k} }$
it follows that:
:$\tuple {s_1, s_2} \in \RR_{\max \set {j, k} }$ and $\tuple {s_2, s_3} \in \RR_{\max \set {j, k} }$
It follows from the method of construction that:
:$\tuple {s_1, s_3} \in \RR_{\max \set {j, k} }$
Hence as $\RR_{\max \set {j, k} } \subseteq \RR^+$, it follows that $\RR^+$ is transitive.
=== Proof of being the smallest such relation ===
Let $\RR'$ be any transitive relation containing $\RR$.
We want to show that $\RR^+ \subseteq \RR'$.
It is sufficient to show that $\forall i \in \N: \RR_i \subseteq \RR'$.
Since $\RR \subseteq \RR'$, we have that $\RR_0 \subseteq \RR'$.
Suppose $\RR_i \subseteq \RR'$.
From the method of construction, as $\RR'$ is transitive:
:$\RR_{i + 1} \subseteq \RR'$
Therefore, by induction:
:$\forall i \in \N: \RR_i \subseteq \RR'$
So $\RR^+ \subseteq \RR'$, and hence the result.
Category:Transitive Closures
Recursive Form of Generalized Termial

== Theorem ==
The termial function as defined on the real numbers fulfils the identity:
:$x? = x + \paren {x - 1}?$
== Proof ==
By definition of the termial on the real numbers:
:$x? = \dfrac {x \paren {x + 1} } 2$
Thus:
== Sources ==
* : $\S 1.2.5$: Permutations and Factorials: Exercise $7$
Category:Termial Function
Recursive Function is Arithmetically Definable

== Theorem ==
Let $f: \N^k \to \N$ be a recursive function.
Then there exists a $\Sigma_1$ WFF of $k + 1$ free variables:
:$\map \phi {y, x_1, x_2, \dotsc, x_k}$
such that:
:$y = \map f {x_1, x_2, \dotsc, x_k} \iff \N \models \map \phi {\sqbrk y, \sqbrk {x_1}, \sqbrk {x_2}, \dotsc, \sqbrk {x_k} }$
where $\sqbrk a$ denotes the unary representation of $a \in \N$.
== Proof ==
By definition of recursive function:
:$f$ can be obtained from basic primitive recursive functions using the operations of:
::substitution
::primitive recursion, and 
::minimization on a function
:a finite number of times.
The existence of $\phi$ follows from:
:Basic Primitive Recursive Functions are Arithmetically Definable
:Substitution of Arithmetically Definable Functions is Arithmetically Definable
:Primitive Recursion on Arithmetically Definable Function is Arithmetically Definable
:Minimization of Arithmetically Definable Function is Arithmetically Definable
Category:Recursive Functions
Recursive Function is URM Computable

== Theorem ==
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.
Category:Recursive Functions
Category:URM Programs
Recursive Function uses One Minimization

== Theorem ==
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}$
Consider the 
From Minimization on Relation Equivalent to Minimization on Function, this is equivalent to:
:$\map {\mu y} {\map {\overline {\operatorname{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 {\operatorname{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}$.
We also know that $\overline {\operatorname{sgn} }$ is primitive recursive.
We also have by hypothesis that $U$ is primitive recursive.
Hence all of $\chi_{T_k}$, $\overline {\operatorname{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.
Category:Recursive Functions
Recursive Relation is Turing Computable

== Theorem ==
Let $f: S \to \set {0, 1}$, where $S \subseteq \N^k$ be a recursive function.
Let the encoding of some $\tuple {x_1, x_2, \dotsc, x_k} \in \N^k$ be the string:
:$1^{x_1} 0 1^{x_2} 0 1^{x_3} 0 \dotsm 0 1^{x_k}$
Then, there exists a Turing machine such that:
* The input symbols of the machine are $\set {0, 1}$
* The accepted language is the set of encodings of $\tuple {x_1, x_2, \dotsc, x_k}$ such that $\map f {x_1, x_2, \dotsc, x_k} = 1$
* The machine halts on an input it is not in the correct format, or it is the encoding of some $\tuple {x_1, x_2, \dotsc, x_k}$ such that $\map f {x_1, x_2, \dotsc, x_k}$ is defined
=== Corollary ===
== Proof ==
Define the function $g: S' \to \set {0, 1}$, where $S \subseteq \N$, as follows:
:$\map g x = \map f {\map {\operatorname{bincode} } {x, 0}, \map {\operatorname{bincode} } {x, 1}, \dotsc, \map {\operatorname{bincode} } {x, k} }$
That is, assuming the input is properly formatted, $g$ takes the value of $f$ when applied to the lengths of the strings of $1$ digits in the base-$2$ representation of the input.
Additionally, from:
* Constant Function is Primitive Recursive
* Primitive Recursive Function is Total Recursive Function
it follows that $g$ is recursive, as it is obtained by substitution on $f$ and other recursive functions.
By Recursive Set is Turing Computable, there exists a Turing machine $T_g$ that computes $g$.
The input is properly formatted it contains exactly $k - 1$ instances of $0$.
By Symbol Count by Finite State Machine, there is a finite state machine $F$ that accepts the number of $0$ symbols in the input is $k - 1$.
By Finite State Machine is Turing Computable, there is a Turing machine $T_F$ that always halts, which performs the same check.
The result follows from Intersection of Turing Machines with $T_g$ and $T_F$.
Category:Recursive Functions
Category:Turing Machines
Recursive Relation is Turing Computable/Corollary

== Theorem ==
Let $f: S \to \set {0, 1}$, where $S \subseteq \N$ be a recursive function.
Let $x \in \N$ be encoded as:
:$1 1 \dotsm 1$
where $1$ is repeated $x$ times.
Then there exists a Turing machine such that:
* The input symbols of the machine are $\set 1$
* The accepted language are the encodings of $x \in \N$ such that $\map f x = 1$
* The machine halts on an input it is the encoding for some $x \in \N$ such that $\map f x$ is defined
== Proof ==
By Recursive Relation is Turing Computable, there is a Turing machine $T$ that satisfies the conditions.
The result follows from an identical machine, except that the input symbols are restricted to be only $\set 1$.
Category:Recursive Functions
Category:Turing Machines