Computability

Computability Theory

Equation form expr-00144a9d86334e0b

h(x,y)≃{undefinedif φx(x)↑g(y)otherwise.h(x,y) \simeq \begin{cases} \text{undefined} & \text{if $\cfind{x}(x) \fundefined$} \\ g(y) & \text{otherwise.} \end{cases}

Read as: h open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: undefined, if partial recursive function phi sub x open parenthesis x close parenthesis is undefined; row two: g open parenthesis y close parenthesis, otherwise; cases end

Means: A source ordered partial or total case definition stating: h open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: undefined, if partial recursive function phi sub x open parenthesis x close parenthesis is undefined; row two: g open parenthesis y close parenthesis, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-03946635ecb87545

f(z)={(z)0if T(e,(z)0,(z)1)aotherwise.f(z) = \begin{cases} (z)_0 & \text{if $T(e,(z)_0,(z)_1)$} \\ a & \text{otherwise.} \end{cases}

Read as: f open parenthesis z close parenthesis equals cases begin; row one: open parenthesis z close parenthesis sub zero, if T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis; row two: a, otherwise; cases end

Means: A source ordered partial or total case definition stating: f open parenthesis z close parenthesis equals cases begin; row one: open parenthesis z close parenthesis sub zero, if T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis; row two: a, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-03fc35a0d47299cc

f(y)≃{k(y)if l(y)=0f(m(y))otherwise.f(y) \simeq \begin{cases} k(y) & \text{if $l(y) = 0$} \\ f(m(y)) & \text{otherwise.} \end{cases}

Read as: f open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: k open parenthesis y close parenthesis, if l open parenthesis y close parenthesis equals zero; row two: f open parenthesis m open parenthesis y close parenthesis close parenthesis, otherwise; cases end

Means: A source ordered partial or total case definition stating: f open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: k open parenthesis y close parenthesis, if l open parenthesis y close parenthesis equals zero; row two: f open parenthesis m open parenthesis y close parenthesis close parenthesis, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-043a718774c572bd

ss

Read as: s

Means: Computability theory notation denoting: s. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

19 occurrences in this chapter

Equation form expr-0521a5cf2b799404

MxM_x

Read as: M sub x

Means: Computability theory notation denoting: M sub x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-05eb9ca75a5f40a2

(z)1(z)_1

Read as: open parenthesis z close parenthesis sub one

Means: Computability theory notation denoting: open parenthesis z close parenthesis sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-06f1a0b63ce8715b

χS(x)={1if x∈S0otherwise\Char{S}(x) = \begin{cases} 1 & \text{if $x \in S$} \\ 0 & \text{otherwise} \end{cases}

Read as: the characteristic function of S open parenthesis x close parenthesis equals cases begin; row one: one, if x is in S; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: the characteristic function of S open parenthesis x close parenthesis equals cases begin; row one: one, if x is in S; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-06f629816495c021

φx(x)↑\cfind{x}(x) \uparrow

Read as: partial recursive function phi sub x open parenthesis x close parenthesis is undefined

Means: A partial computation or program indexing expression stating: partial recursive function phi sub x open parenthesis x close parenthesis is undefined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-073950fc02a4c8b0

x∈Sx \in S

Read as: x is in S

Means: A computability equation or relation stating: x is in S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0771e03eadff1a57

d≃φkd \simeq \cfind{k}

Read as: d has the same definedness and value as partial recursive function phi sub k

Means: A partial computation or program indexing expression stating: d has the same definedness and value as partial recursive function phi sub k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-07746771b4f7a196

1∸χR(x→,y)=01 \tsub \Char{R}(\vec x, y) = 0

Read as: one truncated minus the characteristic function of R open parenthesis vector x comma y close parenthesis equals zero

Means: A computable relation or logical condition stating: one truncated minus the characteristic function of R open parenthesis vector x comma y close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-07843cf21e74cc93

l(x)={f((x)0)if f((x)0)=g((x)1)cotherwise.l(x) = \begin{cases} f((x)_0) & \text{if $f((x)_0) = g((x)_1)$} \\ c & \text{otherwise.} \end{cases}

Read as: l open parenthesis x close parenthesis equals cases begin; row one: f open parenthesis open parenthesis x close parenthesis sub zero close parenthesis, if f open parenthesis open parenthesis x close parenthesis sub zero close parenthesis equals g open parenthesis open parenthesis x close parenthesis sub one close parenthesis; row two: c, otherwise; cases end

Means: A source ordered partial or total case definition stating: l open parenthesis x close parenthesis equals cases begin; row one: f open parenthesis open parenthesis x close parenthesis sub zero close parenthesis, if f open parenthesis open parenthesis x close parenthesis sub zero close parenthesis equals g open parenthesis open parenthesis x close parenthesis sub one close parenthesis; row two: c, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-078d74f6a42e3c45

f(x,y,z)f(x,y,z)

Read as: f open parenthesis x comma y comma z close parenthesis

Means: Computability theory notation denoting: f open parenthesis x comma y comma z close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-07baf0d9fafe5b27

h(e,e)=1h(e,e) = 1

Read as: h open parenthesis e comma e close parenthesis equals one

Means: A computability equation or relation stating: h open parenthesis e comma e close parenthesis equals one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-08a3798ba3aba879

G(k)=0G(k) = 0

Read as: G open parenthesis k close parenthesis equals zero

Means: A computability equation or relation stating: G open parenthesis k close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0904146399813bd8

U(s)U(s)

Read as: U open parenthesis s close parenthesis

Means: Computability theory notation denoting: U open parenthesis s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-090babef241e184b

R(x→,y)R(\vec x, y)

Read as: R open parenthesis vector x comma y close parenthesis

Means: Computability theory notation denoting: R open parenthesis vector x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-093f2182d5bc2fbd

source fragment saying is total followed by closing delimitersis total}}

Read as: source fragment saying is total followed by closing delimiters

Means: This is an exact source only fragment created by nested dollar delimiters in the Rice theorem corollary. Its complete mathematical meaning is supplied only by the disclosed occurrence bound reader formula, while this fragment remains available for source replay.

1 occurrence in this chapter

Equation form expr-0a33d1e7e13354ba

(m+n)(m+n)

Read as: open parenthesis m plus n close parenthesis

Means: Computability theory notation denoting: open parenthesis m plus n close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0bcb02efc3318ba3

φe\cfind{e}

Read as: partial recursive function phi sub e

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0bfe935e70c321c7

uu

Read as: u

Means: Computability theory notation denoting: u. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-0c300b3cff84f7d3

f(1)f(1)

Read as: f open parenthesis one close parenthesis

Means: Computability theory notation denoting: f open parenthesis one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0cf9a00d1baab384

K1={e:∃sT(e,0,s)}K_1 = \Setabs{e}{\lexists[s][T(e,0,s)]}

Read as: K sub one equals the set of e such that there exists s, T open parenthesis e comma zero comma s close parenthesis

Means: An index set or many one reducibility expression stating: K sub one equals the set of e such that there exists s, T open parenthesis e comma zero comma s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-0e4763978622e187

f1f_1

Read as: f sub one

Means: Computability theory notation denoting: f sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-12ed3c090efb7653

⟨x,y⟩∈K0\tuple{x, y} \in K_0

Read as: the tuple x comma y is in K sub zero

Means: An index set or many one reducibility expression stating: the tuple x comma y is in K sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-141fb7638e884e6d

φe(y)≃g(e,y).\cfind{e}(y) \simeq g(e,y).

Read as: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-148de9c5a7a44d19

pp

Read as: p

Means: Computability theory notation denoting: p. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-14d72d2f59750dfd

φx(x)↓\cfind{x}(x) \fdefined

Read as: partial recursive function phi sub x open parenthesis x close parenthesis is defined

Means: A partial computation or program indexing expression stating: partial recursive function phi sub x open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1651321957638729

zero(μsT(x,x,s))\Zero(\umin{s}{T(x,x,s)})

Read as: the constant zero function open parenthesis the least s such that T open parenthesis x comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: the constant zero function open parenthesis the least s such that T open parenthesis x comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1741a20fd8620fe3

f(x)≃g(x)f(x) \simeq g(x)

Read as: f open parenthesis x close parenthesis has the same definedness and value as g open parenthesis x close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis has the same definedness and value as g open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1769b1f15279a8be

smns^m_n

Read as: s superscript m sub n

Means: Computability theory notation denoting: s superscript m sub n. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-177adef74ec71ad9

φe[3](x,y,z)≃φx(y).\cfind{e}[3](x,y,z) \simeq \cfind{x}(y).

Read as: partial recursive function phi sub e at arity three open parenthesis x comma y comma z close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e at arity three open parenthesis x comma y comma z close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-185759f63d5f30c5

φx\cfind{x}

Read as: partial recursive function phi sub x

Means: A partial computation or program indexing expression stating: partial recursive function phi sub x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-189f40034be7a199

jj

Read as: j

Means: Computability theory notation denoting: j. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-18ac3e7343f01689

dd

Read as: d

Means: Computability theory notation denoting: d. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-18f5384d58bcb1bb

YY

Read as: Y

Means: Computability theory notation denoting: Y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1b16b1df538ba12d

nn

Read as: n

Means: Computability theory notation denoting: n. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

17 occurrences in this chapter

Equation form expr-1c19c09eecd5ea8b

g(x)={0if h(x,x)=0↑otherwise.g(x) = \begin{cases} 0 & \text{if $h(x,x) = 0$} \\ \fundefined & \text{otherwise.} \end{cases}

Read as: g open parenthesis x close parenthesis equals cases begin; row one: zero, if h open parenthesis x comma x close parenthesis equals zero; row two: is undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: g open parenthesis x close parenthesis equals cases begin; row one: zero, if h open parenthesis x comma x close parenthesis equals zero; row two: is undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1d60a8815d478306

f(x)={xif χS(x)=1aotherwise.f(x) = \begin{cases} x & \text{if $\Char{S}(x) = 1$} \\ a & \text{otherwise.} \end{cases}

Read as: f open parenthesis x close parenthesis equals cases begin; row one: x, if the characteristic function of S open parenthesis x close parenthesis equals one; row two: a, otherwise; cases end

Means: A source ordered partial or total case definition stating: f open parenthesis x close parenthesis equals cases begin; row one: x, if the characteristic function of S open parenthesis x close parenthesis equals one; row two: a, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1d7aecb5964b6b3d

χA\Char{A}

Read as: the characteristic function of A

Means: A computable relation or logical condition stating: the characteristic function of A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1dbeca42e2c54a76

T(e,x,s)T(e, x, s)

Read as: T open parenthesis e comma x comma s close parenthesis

Means: Computability theory notation denoting: T open parenthesis e comma x comma s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-1dd506c998004ce1

W2W_2

Read as: W sub two

Means: An index set or many one reducibility expression stating: W sub two. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1dffdc9e8f1b8d58

μyf(x→,y)\umin{y}{f(\vec x, y)}

Read as: the least y such that f open parenthesis vector x comma y close parenthesis

Means: A partial computation or program indexing expression stating: the least y such that f open parenthesis vector x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1f2d4073b5029c74

Un(x,x)\fn{Un}(x,x)

Read as: the universal function open parenthesis x comma x close parenthesis

Means: A partial computation or program indexing expression stating: the universal function open parenthesis x comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1f741c85f3d22884

g(x,y)≃Un(f(x),y)g(x,y) \simeq \fn{Un}(f(x),y)

Read as: g open parenthesis x comma y close parenthesis has the same definedness and value as the universal function open parenthesis f open parenthesis x close parenthesis comma y close parenthesis

Means: A partial computation or program indexing expression stating: g open parenthesis x comma y close parenthesis has the same definedness and value as the universal function open parenthesis f open parenthesis x close parenthesis comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-1fcb098cdd009c4b

m=φdm = \cfind{d}

Read as: m equals partial recursive function phi sub d

Means: A partial computation or program indexing expression stating: m equals partial recursive function phi sub d. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-20ab1c5817e4cbc2

h(e,e)=0h(e,e) = 0

Read as: h open parenthesis e comma e close parenthesis equals zero

Means: A computability equation or relation stating: h open parenthesis e comma e close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2203bfc83aefd05f

gcd(u,v)\fn{gcd}(u,v)

Read as: the function gcd open parenthesis u comma v close parenthesis

Means: Computability theory notation denoting: the function gcd open parenthesis u comma v close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2225b5a8bdecda32

x∈Ax \in A

Read as: x is in A

Means: A computability equation or relation stating: x is in A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-2274660f7617e5a7

Un′(e,x)\fn{Un'}(e, x)

Read as: the function Un prime open parenthesis e comma x close parenthesis

Means: Computability theory notation denoting: the function Un prime open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-241d658a47ae5a64

a0a_0

Read as: a sub zero

Means: Computability theory notation denoting: a sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-252f10c83610ebca

ff

Read as: f

Means: Computability theory notation denoting: f. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

55 occurrences in this chapter

Equation form expr-259072e6c653cc56

f(x)f(x)

Read as: f open parenthesis x close parenthesis

Means: Computability theory notation denoting: f open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

7 occurrences in this chapter

Equation form expr-264f2cd5be176c72

(1)⇒(2)(1) \Rightarrow (2)

Read as: open parenthesis one close parenthesis implies open parenthesis two close parenthesis

Means: A computability equation or relation stating: open parenthesis one close parenthesis implies open parenthesis two close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-276c94409042e6a2

f(x)=yf(x) = y

Read as: f open parenthesis x close parenthesis equals y

Means: A computability equation or relation stating: f open parenthesis x close parenthesis equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-28a4891fe37163f1

R(x0,…,xk−1)R(x_0, \dots, x_{k-1})

Read as: R open parenthesis x sub zero comma and so on comma x sub k minus one close parenthesis

Means: Computability theory notation denoting: R open parenthesis x sub zero comma and so on comma x sub k minus one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-28c24d498d4f4597

l(x)=g(diag(x))l(x) = g(\fn{diag}(x))

Read as: l open parenthesis x close parenthesis equals g open parenthesis the function diag open parenthesis x close parenthesis close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: l open parenthesis x close parenthesis equals g open parenthesis the function diag open parenthesis x close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2a43c7b5fb54dad5

φf(e)\cfind{f(e)}

Read as: partial recursive function phi sub f open parenthesis e close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub f open parenthesis e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-2aa80e82da311085

T(e,(z)0,(z)1)T(e,(z)_0,(z)_1)

Read as: T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis

Means: Computability theory notation denoting: T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2b8bddd9d18bb8bf

φe(y)=e+y.\cfind{e}(y) = e + y.

Read as: partial recursive function phi sub e open parenthesis y close parenthesis equals e plus y

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis y close parenthesis equals e plus y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2c705428114fa64b

⌜l⌝\gn{l}

Read as: the Goedel number of l

Means: A fixed point, diagonalization, or lambda calculus expression stating: the Goedel number of l. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2d297d519e4784c5

d(k)↓d(k) \fdefined

Read as: d open parenthesis k close parenthesis is defined

Means: A partial computation or program indexing expression stating: d open parenthesis k close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2d711642b726b044

xx

Read as: x

Means: Computability theory notation denoting: x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

60 occurrences in this chapter

Equation form expr-2e2066dbf9725d59

φk(x)(y)≃{0if x∈K↑otherwise\cfind{k(x)}(y) \simeq \begin{cases}0 & \text{if $x \in K$} \\ \fundefined & \text{otherwise}\end{cases}

Read as: partial recursive function phi sub k open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: zero, if x is in K; row two: is undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: partial recursive function phi sub k open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: zero, if x is in K; row two: is undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2e7d2c03a9507ae2

cc

Read as: c

Means: Computability theory notation denoting: c. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-2eb8b9099303d168

φd\cfind{d}

Read as: partial recursive function phi sub d

Means: A partial computation or program indexing expression stating: partial recursive function phi sub d. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-2f124b83a3e1c1cb

(2)⇒(1)(2) \Rightarrow (1)

Read as: open parenthesis two close parenthesis implies open parenthesis one close parenthesis

Means: A computability equation or relation stating: open parenthesis two close parenthesis implies open parenthesis one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2f47128affcefb8a

s(x,y)≃Un2(x,x,y),s(x,y) \simeq \fn{Un}^2(x,x,y),

Read as: s open parenthesis x comma y close parenthesis has the same definedness and value as the function Un superscript two open parenthesis x comma x comma y close parenthesis

Means: A partial computation or program indexing expression stating: s open parenthesis x comma y close parenthesis has the same definedness and value as the function Un superscript two open parenthesis x comma x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2f6b5c0f84584144

fkf_k

Read as: f sub k

Means: Computability theory notation denoting: f sub k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-2f86e39b0fe2be69

source closing delimiter fragment}}

Read as: source closing delimiter fragment

Means: This is an exact source only fragment created by nested dollar delimiters in the Rice theorem corollary. Its complete mathematical meaning is supplied only by the disclosed occurrence bound reader formula, while this fragment remains available for source replay.

2 occurrences in this chapter

Equation form expr-301651c844979674

h(e,x)h(e,x)

Read as: h open parenthesis e comma x close parenthesis

Means: Computability theory notation denoting: h open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-316779d1e4588b71

fe(x)f_e(x)

Read as: f sub e open parenthesis x close parenthesis

Means: Computability theory notation denoting: f sub e open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3278d314268082cb

A={n:φn∈C}A = \Setabs{n}{\cfind{n} \in C}

Read as: A equals the set of n such that partial recursive function phi sub n is in C

Means: An index set or many one reducibility expression stating: A equals the set of n such that partial recursive function phi sub n is in C. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-32b3b38bf69c8391

S={x:x∉x}S = \Setabs{x}{x \notin x}

Read as: S equals the set of x such that x is not in x

Means: An index set or many one reducibility expression stating: S equals the set of x such that x is not in x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-32d395cd3caf1e6f

Un\fn{Un}

Read as: the function Un

Means: A partial computation or program indexing expression stating: the function Un. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-333e0a1e27815d0c

GG

Read as: G

Means: Computability theory notation denoting: G. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

8 occurrences in this chapter

Equation form expr-33ad76969151f2c4

⟨e,x⟩∈K0\tuple{e,x} \in K_0

Read as: the tuple e comma x is in K sub zero

Means: An index set or many one reducibility expression stating: the tuple e comma x is in K sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3432408e34956dfa

B=We={x:φe(x)↓}.B = W_e = \Setabs{x}{\cfind{e}(x) \fdefined}.

Read as: B equals W sub e equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: B equals W sub e equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-35ffec652038ba32

φe(y)≃Un(f(e),y)≃φf(e)(y).\cfind{e}(y) & \simeq \fn{Un}(f(e),y) \\ & \simeq \cfind{f(e)}(y).

Read as: partial recursive function phi sub e open parenthesis y close parenthesis then has the same definedness and value as the universal function open parenthesis f open parenthesis e close parenthesis comma y close parenthesis next row then has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis

Means: A source ordered calculation or equivalence chain stating: partial recursive function phi sub e open parenthesis y close parenthesis then has the same definedness and value as the universal function open parenthesis f open parenthesis e close parenthesis comma y close parenthesis next row then has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-36473535dabf4171

⟨x,y⟩\tuple{x, y}

Read as: the tuple x comma y

Means: Computability theory notation denoting: the tuple x comma y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-36d884ad81c0ef6a

WxW_x

Read as: W sub x

Means: An index set or many one reducibility expression stating: W sub x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-385262088dac5789

Y=(λxg.g(xxg))(λxg.g(xxg))Y = (\lambd[xg][g(xxg)])(\lambd[xg][g(xxg)])

Read as: Y equals the self application of lambda x and g, g applied to x applied to x applied to g

Means: A fixed point, diagonalization, or lambda calculus expression stating: Y equals the self application of lambda x and g, g applied to x applied to x applied to g. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-39cce35be825b834

φk(x)≃Un(k,x)\cfind{k}(x) \simeq \fn{Un}(k, x)

Read as: partial recursive function phi sub k open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis k comma x close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub k open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis k comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-39d78289290c8b72

A≡mBA \equiv_m B

Read as: A is many one equivalent to B

Means: An index set or many one reducibility expression stating: A is many one equivalent to B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3b2591dd01df745a

x∈Bx \in B

Read as: x is in B

Means: A computability equation or relation stating: x is in B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3b5a7ed830fe3419

f(z)={U((z)1)if T(e,(z)0,(z)1)aotherwise.f(z) = \begin{cases} U((z)_1) & \text{if $T(e, (z)_0, (z)_1)$} \\ a & \text{otherwise.} \end{cases}

Read as: f open parenthesis z close parenthesis equals cases begin; row one: U open parenthesis open parenthesis z close parenthesis sub one close parenthesis, if T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis; row two: a, otherwise; cases end

Means: A source ordered partial or total case definition stating: f open parenthesis z close parenthesis equals cases begin; row one: U open parenthesis open parenthesis z close parenthesis sub one close parenthesis, if T open parenthesis e comma open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one close parenthesis; row two: a, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3ba9dcc1da00e52b

source opening set builder fragment\Setabs{x}{\text{

Read as: source opening set builder fragment

Means: This is an exact source only fragment created by nested dollar delimiters in the Rice theorem corollary. Its complete mathematical meaning is supplied only by the disclosed occurrence bound reader formula, while this fragment remains available for source replay.

3 occurrences in this chapter

Equation form expr-3bdc55e2c2a897b2

f(x)≃U(μsT(e,x,s))f(x) \simeq U(\umin{s}{T(e, x, s)})

Read as: f open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3cca59268b91ea0b

φx(y)\cfind{x}(y)

Read as: partial recursive function phi sub x open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub x open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-3d0a5c111af3df71

d(x)d(x)

Read as: d open parenthesis x close parenthesis

Means: Computability theory notation denoting: d open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3ee6764d00e1e26f

g(x,y)≃{k(y)if l(y)=0φx(m(y))otherwiseg(x,y) \simeq \begin{cases} k(y) & \text{if $l(y) = 0$} \\ \cfind{x}(m(y)) & \text{otherwise} \end{cases}

Read as: g open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: k open parenthesis y close parenthesis, if l open parenthesis y close parenthesis equals zero; row two: partial recursive function phi sub x open parenthesis m open parenthesis y close parenthesis close parenthesis, otherwise; cases end

Means: A source ordered partial or total case definition stating: g open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: k open parenthesis y close parenthesis, if l open parenthesis y close parenthesis equals zero; row two: partial recursive function phi sub x open parenthesis m open parenthesis y close parenthesis close parenthesis, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-3f79bb7b435b0532

ee

Read as: e

Means: Computability theory notation denoting: e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

41 occurrences in this chapter

Equation form expr-40092fb12ce7d2b9

We={x:φe(x)↓}.W_e = \Setabs{x}{\cfind{e}(x) \fdefined}.

Read as: W sub e equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: W sub e equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-40ee502b1cbe41c4

fx(y)≃φx(x,y)f_x(y) \simeq \cfind{x}(x,y)

Read as: f sub x open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis x comma y close parenthesis

Means: A partial computation or program indexing expression stating: f sub x open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-414fb248b29f8870

φf(x)(y)≃g(x,y)\cfind{f(x)}(y) \simeq g(x,y)

Read as: partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as g open parenthesis x comma y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as g open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-416a48c668bf122a

S∈SS \in S

Read as: S is in S

Means: A computability equation or relation stating: S is in S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-41a50e1184a5cab3

φk(k)↑\cfind{k}(k) \fundefined

Read as: partial recursive function phi sub k open parenthesis k close parenthesis is undefined

Means: A partial computation or program indexing expression stating: partial recursive function phi sub k open parenthesis k close parenthesis is undefined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-428459f7dd087b9a

f(z)f(z)

Read as: f open parenthesis z close parenthesis

Means: Computability theory notation denoting: f open parenthesis z close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-447ae449b1bb55f1

x∈A¯x \in \Complement{A}

Read as: x is in the complement of A

Means: An index set or many one reducibility expression stating: x is in the complement of A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-44bd7ae60f478fae

HH

Read as: H

Means: Computability theory notation denoting: H. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

5 occurrences in this chapter

Equation form expr-45bc21a62f75673a

φs(e,x)(y)≃hx(y)\cfind{s(e,x)}(y) \simeq h_x(y)

Read as: partial recursive function phi sub s open parenthesis e comma x close parenthesis open parenthesis y close parenthesis has the same definedness and value as h sub x open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub s open parenthesis e comma x close parenthesis open parenthesis y close parenthesis has the same definedness and value as h sub x open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-46474c5e2b19058b

F(F)=1F(F) = 1

Read as: F open parenthesis F close parenthesis equals one

Means: A computability equation or relation stating: F open parenthesis F close parenthesis equals one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4725dd93d0126f4d

f(x)≃μyR(x,y).f(x) \simeq \umin{y}{R(x, y)}.

Read as: f open parenthesis x close parenthesis has the same definedness and value as the least y such that R open parenthesis x comma y close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis has the same definedness and value as the least y such that R open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-47e8e6cc3298a371

G(x)={1if fx(x)↓=00otherwiseG(x) = \begin{cases} 1 & \text{if $f_x(x)\downarrow = 0$} \\ 0 & \text{otherwise} \end{cases}

Read as: G open parenthesis x close parenthesis equals cases begin; row one: one, if f sub x open parenthesis x close parenthesis is defined and equals zero; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: G open parenthesis x close parenthesis equals cases begin; row one: one, if f sub x open parenthesis x close parenthesis is defined equals zero; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-48d63670910eb094

χA=1∸χA¯\Char{A} = 1 \tsub \Char{\Complement{A}}

Read as: the characteristic function of A equals one truncated minus the characteristic function of the complement of A

Means: An index set or many one reducibility expression stating: the characteristic function of A equals one truncated minus the characteristic function of the complement of A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-48dc92a98cff75ec

fef_e

Read as: f sub e

Means: Computability theory notation denoting: f sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-491de28f36a3e353

yn−1y_{n-1}

Read as: y sub n minus one

Means: Computability theory notation denoting: y sub n minus one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-496baf967c85e923

f(x,y,z)≃φx(y).f(x,y,z) \simeq \cfind{x}(y).

Read as: f open parenthesis x comma y comma z close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x comma y comma z close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-498bb50082997c28

⟨u,v⟩\tuple{u, v}

Read as: the tuple u comma v

Means: Computability theory notation denoting: the tuple u comma v. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4b5ef95fee7e4c9e

φs(e,x,y)(0)↓if and only ifφx(y)↓.\cfind{s(e,x,y)}(0) \fdefined \quad \text{if and only if} \quad \cfind{x}(y) \fdefined.

Read as: partial recursive function phi sub s open parenthesis e comma x comma y close parenthesis open parenthesis zero close parenthesis is defined if and only if partial recursive function phi sub x open parenthesis y close parenthesis is defined

Means: A partial computation or program indexing expression stating: partial recursive function phi sub s open parenthesis e comma x comma y close parenthesis open parenthesis zero close parenthesis is defined if and only if partial recursive function phi sub x open parenthesis y close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4bd1481f72d38499

gcd\fn{gcd}

Read as: the function gcd

Means: Computability theory notation denoting: the function gcd. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-4bd7e733b1e3b126

source fragment saying is constant followed by closing delimitersis constant}}

Read as: source fragment saying is constant followed by closing delimiters

Means: This is an exact source only fragment created by nested dollar delimiters in the Rice theorem corollary. Its complete mathematical meaning is supplied only by the disclosed occurrence bound reader formula, while this fragment remains available for source replay.

1 occurrence in this chapter

Equation form expr-4c94485e0c21ae6c

vv

Read as: v

Means: Computability theory notation denoting: v. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4ce3309795b4e2ac

s(e,x)s(e,x)

Read as: s open parenthesis e comma x close parenthesis

Means: Computability theory notation denoting: s open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-4ddd6f419b334e54

f(x)↓f(x) \fdefined

Read as: f open parenthesis x close parenthesis is defined

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4e07408562bedb8b

33

Read as: three

Means: Computability theory notation denoting: three. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-4f5e2d40ae65b9ba

Un′(k,x)\fn{Un}'(k,x)

Read as: the function Un prime open parenthesis k comma x close parenthesis

Means: A partial computation or program indexing expression stating: the function Un prime open parenthesis k comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-51d8c66e0602bb4e

f(0)f(0)

Read as: f open parenthesis zero close parenthesis

Means: Computability theory notation denoting: f open parenthesis zero close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-540277dcc25be7ec

⌜φe(e)⌝\gn{\cfind{e}(e)}

Read as: the Goedel number of partial recursive function phi sub e open parenthesis e close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: the Goedel number of partial recursive function phi sub e open parenthesis e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-559aead08264d579

AA

Read as: A

Means: Computability theory notation denoting: A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

64 occurrences in this chapter

Equation form expr-56c400b589975005

G(k)=1G(k) = 1

Read as: G open parenthesis k close parenthesis equals one

Means: A computability equation or relation stating: G open parenthesis k close parenthesis equals one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-584941ab91a254df

smn(e,a0,…,am−1)s^m_n(e, a_0, \dots, a_{m-1})

Read as: s superscript m sub n open parenthesis e comma a sub zero comma and so on comma a sub m minus one close parenthesis

Means: Computability theory notation denoting: s superscript m sub n open parenthesis e comma a sub zero comma and so on comma a sub m minus one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-594e519ae499312b

zz

Read as: z

Means: Computability theory notation denoting: z. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

5 occurrences in this chapter

Equation form expr-5b93a9b0461acefd

YgYg

Read as: Y applied to g

Means: Computability theory notation denoting: Y applied to g. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-5ccb84c570fcf376

x→\vec x

Read as: vector x

Means: Computability theory notation denoting: vector x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5d18a8592d1b90e7

g(x)≃f((x)0,(x)1,(x)2)g(x) \simeq f((x)_0, (x)_1, (x)_2)

Read as: g open parenthesis x close parenthesis has the same definedness and value as f open parenthesis open parenthesis x close parenthesis sub zero comma open parenthesis x close parenthesis sub one comma open parenthesis x close parenthesis sub two close parenthesis

Means: A partial computation or program indexing expression stating: g open parenthesis x close parenthesis has the same definedness and value as f open parenthesis open parenthesis x close parenthesis sub zero comma open parenthesis x close parenthesis sub one comma open parenthesis x close parenthesis sub two close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5d4d681c3011bb1a

φf(x)(0)\cfind{f(x)}(0)

Read as: partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis zero close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis zero close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5d9b8d1482b25398

φf(e)(0)\cfind{f(e)}(0)

Read as: partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis zero close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis zero close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-5f3f93ceb6af555d

smn(e,a0,…,am−1)s^m_n(e, a_0, \dots, a_{m-1})

Read as: s superscript m sub n open parenthesis e comma a sub zero comma and so on comma a sub m minus one close parenthesis

Means: Computability theory notation denoting: s superscript m sub n open parenthesis e comma a sub zero comma and so on comma a sub m minus one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5f75e667b02a4f2e

φk(x)\cfind{k(x)}

Read as: partial recursive function phi sub k open parenthesis x close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub k open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5f7f29e2bbd06ccc

U(s)=yU(s) = y

Read as: U open parenthesis s close parenthesis equals y

Means: A computability equation or relation stating: U open parenthesis s close parenthesis equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-5f93da3d097ee385

f(x→,0)f(\vec x, 0)

Read as: f open parenthesis vector x comma zero close parenthesis

Means: Computability theory notation denoting: f open parenthesis vector x comma zero close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5fe6dc6b2281b3d2

zero\Zero

Read as: the constant zero function

Means: Computability theory notation denoting: the constant zero function. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-5feceb66ffc86f38

00

Read as: zero

Means: Computability theory notation denoting: zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

15 occurrences in this chapter

Equation form expr-60988e2d2c7297d0

g(x,y)≃{0if y=0 and φf(x)(0)↓=0undefinedotherwise.g(x,y) \simeq \begin{cases} 0 & \text{if $y=0$ and $\cfind{f(x)}(0) \fdefined = 0$} \\ \text{undefined} & \text{otherwise.} \end{cases}

Read as: g open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: zero, if y equals zero and partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis zero close parenthesis is defined and equals zero; row two: undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: g open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: zero, if y equals zero and partial recursive function phi sub f open parenthesis x close parenthesis open parenthesis zero close parenthesis is defined equals zero; row two: undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-6189268380e19b7e

χK\Char{K}

Read as: the characteristic function of K

Means: A computable relation or logical condition stating: the characteristic function of K. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-618eb1b2a3b4a78c

Un2\fn{Un}^2

Read as: the function Un superscript two

Means: A partial computation or program indexing expression stating: the function Un superscript two. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-61b460112672f1fd

y=ay = a

Read as: y equals a

Means: A computability equation or relation stating: y equals a. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-62c66a7a5dd70c31

mm

Read as: m

Means: Computability theory notation denoting: m. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

16 occurrences in this chapter

Equation form expr-63b492eee1028e2e

h(x,y)≃P02(g(y),Un(x,x)).h(x,y) \simeq \Proj{2}{0}(g(y),\fn{Un}(x,x)).

Read as: h open parenthesis x comma y close parenthesis has the same definedness and value as the two place projection with index zero open parenthesis g open parenthesis y close parenthesis comma the universal function open parenthesis x comma x close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: h open parenthesis x comma y close parenthesis has the same definedness and value as the two place projection with index zero open parenthesis g open parenthesis y close parenthesis comma the universal function open parenthesis x comma x close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-64ea89e65055a0fa

y=f(⟨x,s⟩)y = f(\tuple{x,s})

Read as: y equals f open parenthesis the tuple x comma s close parenthesis

Means: A computability equation or relation stating: y equals f open parenthesis the tuple x comma s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-654074d78f76a4ba

G:ℕ→{0,1}G \colon \Nat \to \{ 0, 1 \}

Read as: G from the natural numbers to the set containing zero and one

Means: A set-valued computability expression stating: G from the natural numbers to the set containing zero and one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-65e250c2f2829fd8

T(e,x,s)T(e,x,s)

Read as: T open parenthesis e comma x comma s close parenthesis

Means: Computability theory notation denoting: T open parenthesis e comma x comma s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-661674f970e6fab8

A≤mBA \leq_m B

Read as: A is many one reducible to B

Means: An index set or many one reducibility expression stating: A is many one reducible to B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

5 occurrences in this chapter

Equation form expr-66ff1477fbad92f2

h(⌜φx(y)⌝)={1if φx(y)↓0otherwise.h(\gn{\cfind{x}(y)}) = \begin{cases} 1 & \text{if $\cfind{x}(y) \fdefined$} \\ 0 & \text{otherwise.} \end{cases}

Read as: h open parenthesis the Goedel number of partial recursive function phi sub x open parenthesis y close parenthesis close parenthesis equals cases begin; row one: one, if partial recursive function phi sub x open parenthesis y close parenthesis is defined; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: h open parenthesis the Goedel number of partial recursive function phi sub x open parenthesis y close parenthesis close parenthesis equals cases begin; row one: one, if partial recursive function phi sub x open parenthesis y close parenthesis is defined; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-68c0df64471a7f09

A∪BA \cup B

Read as: A union B

Means: Computability theory notation denoting: A union B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

6 occurrences in this chapter

Equation form expr-691974c5aa2ef0bb

f(x→,y−1)f(\vec x, y-1)

Read as: f open parenthesis vector x comma y minus one close parenthesis

Means: Computability theory notation denoting: f open parenthesis vector x comma y minus one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-6b23c0d5f35d1b11

CC

Read as: C

Means: Computability theory notation denoting: C. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

14 occurrences in this chapter

Equation form expr-6b86b273ff34fce1

11

Read as: one

Means: Computability theory notation denoting: one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-6bf7cbf3c883ca8a

S={x:φe(x)↓}.S = \Setabs{x}{\cfind{e}(x) \fdefined}.

Read as: S equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: S equals the set of x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-6c44ce5e84e8987a

g(e)g(e)

Read as: g open parenthesis e close parenthesis

Means: Computability theory notation denoting: g open parenthesis e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-6ce19e3bc5fa63a0

Un′(e,x)\fn{Un'}(e,x)

Read as: the function Un prime open parenthesis e comma x close parenthesis

Means: Computability theory notation denoting: the function Un prime open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-6f1b3a918507a187

φe(x)≃U(μsT(e,x,s))\cfind{e}(x) \simeq U(\umin{s}{T(e,x,s)})

Read as: partial recursive function phi sub e open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-72e211307fb8648d

e=diag(⌜l⌝)e = \fn{diag}(\gn{l})

Read as: e equals the function diag open parenthesis the Goedel number of l close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: e equals the function diag open parenthesis the Goedel number of l close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-746210d8828e809e

μyR(x→,y)\umin{y}{R(\vec x, y)}

Read as: the least y such that R open parenthesis vector x comma y close parenthesis

Means: A partial computation or program indexing expression stating: the least y such that R open parenthesis vector x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-74662e64a87200e0

A¯=ℕ∖A\Complement{A} = \Nat \setminus A

Read as: the complement of A equals the natural numbers set minus A

Means: An index set or many one reducibility expression stating: the complement of A equals the natural numbers set minus A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-75d9f9fb3b813d8e

getinput\fn{getinput}

Read as: the function getinput

Means: Computability theory notation denoting: the function getinput. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-76590df9d2a2ab5a

g(w)=s(e,(w)0,(w)1)g(w) = s(e,(w)_0,(w)_1)

Read as: g open parenthesis w close parenthesis equals s open parenthesis e comma open parenthesis w close parenthesis sub zero comma open parenthesis w close parenthesis sub one close parenthesis

Means: A computability equation or relation stating: g open parenthesis w close parenthesis equals s open parenthesis e comma open parenthesis w close parenthesis sub zero comma open parenthesis w close parenthesis sub one close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-76e79112451c8ff4

g(x)≃Un(e,x)g(x) \simeq \fn{Un}(e, x)

Read as: g open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis e comma x close parenthesis

Means: A partial computation or program indexing expression stating: g open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-77405756466253f1

g(0,e,x)≃0g(y+1,e,x)≃Un(e,x);g(0, e, x) & \simeq 0 \\ g(y+1, e, x) & \simeq \fn{Un}(e,x);

Read as: g of zero, e, and x is zero; and g of y plus one, e, and x agrees in definedness and value with the universal computation at e and x

Means: A source ordered calculation or equivalence chain stating: g of zero, e, and x is zero; and g of y plus one, e, and x agrees in definedness and value with the universal computation at e and x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-77c413b453e89606

Yg≡βg(Yg)Yg \equiv_\beta g(Yg)

Read as: Y applied to g is beta equivalent to g applied to Y applied to g

Means: A fixed point, diagonalization, or lambda calculus expression stating: Y applied to g is beta equivalent to g applied to Y applied to g. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-7923c2b6505b5b23

ge(y)≃g(e,y)g_e(y) \simeq g(e,y)

Read as: g sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis

Means: A partial computation or program indexing expression stating: g sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-79d4c7f9c8579543

ℕ\Nat

Read as: the natural numbers

Means: Computability theory notation denoting: the natural numbers. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-7a03384e6e8b8519

≤\le

Read as: is less than or equal to

Means: Computability theory notation denoting: is less than or equal to. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-7b90030a180b148d

f(x)≃Un(x,x)+1f(x) \simeq \fn{Un}(x,x)+1

Read as: f open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis x comma x close parenthesis plus one

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis x comma x close parenthesis plus one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-7c5e2a434ad1c219

φe(x)=y\cfind{e}(x) = y

Read as: partial recursive function phi sub e open parenthesis x close parenthesis equals y

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-7c790e9fb2ad5aec

f:A→Bf\colon A \to B

Read as: f from A to B

Means: Computability theory notation denoting: f from A to B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-7eb7d9080de7a6a0

{k}\{ k \}

Read as: the singleton set containing k

Means: A set expression denoting the singleton set containing k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-80759daa1178b685

{⟨e,x⟩:φe(x)↓}\Setabs{\tuple{e, x}}{\cfind{e}(x) \fdefined}

Read as: the set of the tuple e comma x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: the set of the tuple e comma x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-80981b8364c29483

⟨x,x⟩\tuple{x, x}

Read as: the tuple x comma x

Means: Computability theory notation denoting: the tuple x comma x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-817ffd3f35e344f5

l(x,y)≃g(diag(x),y).l(x,y) \simeq g(\fn{diag}(x),y).

Read as: l open parenthesis x comma y close parenthesis has the same definedness and value as g open parenthesis the function diag open parenthesis x close parenthesis comma y close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: l open parenthesis x comma y close parenthesis has the same definedness and value as g open parenthesis the function diag open parenthesis x close parenthesis comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-8254c329a92850f6

kk

Read as: k

Means: Computability theory notation denoting: k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

13 occurrences in this chapter

Equation form expr-83c049116539984b

P02(z0,z1)=z0\Proj{2}{0}(z_0, z_1) = z_0

Read as: the two place projection with index zero open parenthesis z sub zero comma z sub one close parenthesis equals z sub zero

Means: A computability equation or relation stating: the two place projection with index zero open parenthesis z sub zero comma z sub one close parenthesis equals z sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-859e2d71f9a5d89f

h(e,e)≠0h(e,e) \neq 0

Read as: h open parenthesis e comma e close parenthesis is not equal to zero

Means: Computability theory notation denoting: h open parenthesis e comma e close parenthesis is not equal to zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-86be9a55762d316a

KK

Read as: K

Means: Computability theory notation denoting: K. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

14 occurrences in this chapter

Equation form expr-8ac0489d44c4061d

f(x)=μyT(x,x,y)f(x) = \umin{y}{T(x,x,y)}

Read as: f open parenthesis x close parenthesis equals the least y such that T open parenthesis x comma x comma y close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis equals the least y such that T open parenthesis x comma x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-8bab7505b45d972a

K0={⟨e,x⟩:φe(x)↓},K_0 = \Setabs{\tuple{e, x}}{\cfind{e}(x) \fdefined },

Read as: K sub zero equals the set of the tuple e comma x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: K sub zero equals the set of the tuple e comma x such that partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-8c2574892063f995

RR

Read as: R

Means: Computability theory notation denoting: R. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-8de0b3c47f112c59

SS

Read as: S

Means: Computability theory notation denoting: S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

37 occurrences in this chapter

Equation form expr-8e38081a5adb4c64

f(e)f(e)

Read as: f open parenthesis e close parenthesis

Means: Computability theory notation denoting: f open parenthesis e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-8e95f7550afca27a

T(d,x,h(x))T(d, x, h(x))

Read as: T open parenthesis d comma x comma h open parenthesis x close parenthesis close parenthesis

Means: Computability theory notation denoting: T open parenthesis d comma x comma h open parenthesis x close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-91f26b0ee660f0bf

h(x)=μy(f(y)=x∨g(y)=x) andj(x)=μy(f((y)0)=x∧g((y)1)=x).h(x) & = \umin{y}{(f(y) = x \lor g(y) = x)} \text{ and}\\ j(x) & = \umin{y}{(f((y)_0) = x \land g((y)_1) = x)}.

Read as: h of x is the least y for which f of y equals x or g of y equals x; and j of x is the least coded pair of stages at which both f and g equal x

Means: A source ordered calculation or equivalence chain stating: h of x is the least y for which f of y equals x or g of y equals x; and j of x is the least coded pair of stages at which both f and g equal x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-92808bf5ecf3acd9

j(y)=0j(y) = 0

Read as: j open parenthesis y close parenthesis equals zero

Means: A computability equation or relation stating: j open parenthesis y close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-92fa3711183bd368

print(x,y)\fn{print}(x,y)

Read as: the function print open parenthesis x comma y close parenthesis

Means: Computability theory notation denoting: the function print open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9312763cb0d2c90b

(z)0(z)_0

Read as: open parenthesis z close parenthesis sub zero

Means: Computability theory notation denoting: open parenthesis z close parenthesis sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-93b91265eff125c7

g∘f\comp{f}{g}

Read as: g composed after f

Means: Computability theory notation denoting: g composed after f. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-942d6d9a4ea56ce8

Un′(k,x)\fn{Un}'(k, x)

Read as: the function Un prime open parenthesis k comma x close parenthesis

Means: A partial computation or program indexing expression stating: the function Un prime open parenthesis k comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-948eb931e36269e8

hx(y)≃h(x,y)h_x(y) \simeq h(x,y)

Read as: h sub x open parenthesis y close parenthesis has the same definedness and value as h open parenthesis x comma y close parenthesis

Means: A partial computation or program indexing expression stating: h sub x open parenthesis y close parenthesis has the same definedness and value as h open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-95fbd9528e73ef30

f(x→,y)=0f(\vec x, y) = 0

Read as: f open parenthesis vector x comma y close parenthesis equals zero

Means: A computability equation or relation stating: f open parenthesis vector x comma y close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-966274ec1428434c

φe(y)≃φf(e)(y)≃g(e,y).\cfind{e}(y) & \simeq \cfind{f(e)}(y) \\ & \simeq g(e,y).

Read as: partial recursive function phi sub e open parenthesis y close parenthesis then has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis next row then has the same definedness and value as g open parenthesis e comma y close parenthesis

Means: A source ordered calculation or equivalence chain stating: partial recursive function phi sub e open parenthesis y close parenthesis then has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis next row then has the same definedness and value as g open parenthesis e comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9762a290c77f76de

d(x)=Un′(x,x)+1d(x) = \fn{Un}'(x, x) + 1

Read as: d open parenthesis x close parenthesis equals the function Un prime open parenthesis x comma x close parenthesis plus one

Means: A partial computation or program indexing expression stating: d open parenthesis x close parenthesis equals the function Un prime open parenthesis x comma x close parenthesis plus one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-982d20d1e491c9e1

f:ℕ→ℕf\colon \Nat \to \Nat

Read as: f from the natural numbers to the natural numbers

Means: Computability theory notation denoting: f from the natural numbers to the natural numbers. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-98550483d35bb33d

f2f_2

Read as: f sub two

Means: Computability theory notation denoting: f sub two. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-988faa2b83499ddd

WeW_e

Read as: W sub e

Means: An index set or many one reducibility expression stating: W sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

5 occurrences in this chapter

Equation form expr-98f83007a7c5cb36

φk\cfind{k}

Read as: partial recursive function phi sub k

Means: A partial computation or program indexing expression stating: partial recursive function phi sub k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-993dfacb9c1d5689

g(x,y)g(x,y)

Read as: g open parenthesis x comma y close parenthesis

Means: Computability theory notation denoting: g open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-9953db2591e9cd26

mod(v,u)\fn{mod}(v, u)

Read as: the function mod open parenthesis v comma u close parenthesis

Means: Computability theory notation denoting: the function mod open parenthesis v comma u close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9958f44f8ed10979

χA=χB∘f\Char{A} = \comp{f}{\Char{B}}

Read as: the characteristic function of A equals the characteristic function of B composed after f

Means: A computable relation or logical condition stating: the characteristic function of A equals the characteristic function of B composed after f. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-9c5c098d009032a0

am−1a_{m-1}

Read as: a sub m minus one

Means: Computability theory notation denoting: a sub m minus one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-9dbb3196ad23c876

x∈A iff f(x)∈B iff g(f(x))↓.x \in A & \text{ iff } f(x) \in B \\ & \text{ iff } g(f(x)) \fdefined.

Read as: x belongs to A exactly when f of x belongs to B, exactly when g is defined at f of x

Means: A source ordered calculation or equivalence chain stating: x belongs to A exactly when f of x belongs to B, exactly when g is defined at f of x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9df210b780a2c75d

χS\Char{S}

Read as: the characteristic function of S

Means: A computable relation or logical condition stating: the characteristic function of S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9df361b4e347d18b

k=(λx.g(xx))(λx.g(xx))→βg((λx.g(xx))(λx.g(xx)))=gk.k & = (\lambd[x][g(xx)])(\lambd[x][g(xx)]) \\ & \red g((\lambd[x][g(xx)])(\lambd[x][g(xx)])) \\ & = gk.

Read as: k equals the self application of lambda x, g applied to x applied to x; this beta reduces to g applied to that self application; hence k equals g applied to k

Means: A source ordered calculation or equivalence chain stating: k equals the self application of lambda x, g applied to x applied to x; this beta reduces to g applied to that self application; hence k equals g applied to k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-9e3a6b4e0fa34d4b

φe(x)\cfind{e}(x)

Read as: partial recursive function phi sub e open parenthesis x close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-9f98bf17d1aba3ee

f(⟨e,x⟩)f(\tuple{e, x})

Read as: f open parenthesis the tuple e comma x close parenthesis

Means: Computability theory notation denoting: f open parenthesis the tuple e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-9ffa3ca7f1cce887

Un(e,x)\fn{Un}(e,x)

Read as: the universal function open parenthesis e comma x close parenthesis

Means: A partial computation or program indexing expression stating: the universal function open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

5 occurrences in this chapter

Equation form expr-a1fce4363854ff88

yy

Read as: y

Means: Computability theory notation denoting: y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

31 occurrences in this chapter

Equation form expr-a2277e0b98ac28a5

g(x)g(x)

Read as: g open parenthesis x close parenthesis

Means: Computability theory notation denoting: g open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a25513c7e0f6eaa8

UU

Read as: U

Means: Computability theory notation denoting: U. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

9 occurrences in this chapter

Equation form expr-a3790cd28ac3b155

f(x→,y)f(\vec x, y)

Read as: f open parenthesis vector x comma y close parenthesis

Means: Computability theory notation denoting: f open parenthesis vector x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a39b32492df35396

gkgk

Read as: g applied to k

Means: Computability theory notation denoting: g applied to k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a45eebdf2ae1fe3c

m(x)+n(x)m(x) + n(x)

Read as: m open parenthesis x close parenthesis plus n open parenthesis x close parenthesis

Means: Computability theory notation denoting: m open parenthesis x close parenthesis plus n open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a4b2094915c65384

φe(y)≃φf(e)(y).\cfind{e}(y) \simeq \cfind{f(e)}(y).

Read as: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a4e5a4d98ea7c07e

μyh(x,x)=0\umin{y}{h(x,x) = 0}

Read as: the least y such that h open parenthesis x comma x close parenthesis equals zero

Means: A partial computation or program indexing expression stating: the least y such that h open parenthesis x comma x close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a5ec8edf5fd5218f

S={x:∃yR(x,y)}.S = \Setabs{ x }{ \lexists[y][R(x,y)] }.

Read as: S equals the set of x such that there exists y, R open parenthesis x comma y close parenthesis

Means: An index set or many one reducibility expression stating: S equals the set of x such that there exists y, R open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a603e6b6eedcb75f

MeM_e

Read as: M sub e

Means: Computability theory notation denoting: M sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-a624837080e38223

⟨e,x⟩\tuple{e, x}

Read as: the tuple e comma x

Means: Computability theory notation denoting: the tuple e comma x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a75dbfeaae9c1c65

f0f_0

Read as: f sub zero

Means: Computability theory notation denoting: f sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-a7adb53654498773

g(y)g(y)

Read as: g open parenthesis y close parenthesis

Means: Computability theory notation denoting: g open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-a86d6b6a8e6757bb

h(x,y)h(x,y)

Read as: h open parenthesis x comma y close parenthesis

Means: Computability theory notation denoting: h open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

7 occurrences in this chapter

Equation form expr-a95ee47e79696f06

B≤mAB \leq_m A

Read as: B is many one reducible to A

Means: An index set or many one reducibility expression stating: B is many one reducible to A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a98c0d9587abdd82

0=00 = 0

Read as: zero equals zero

Means: A computability equation or relation stating: zero equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-a9f51566bd6705f7

EE

Read as: E

Means: Computability theory notation denoting: E. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-aa0252d75597a0e1

=y= y

Read as: equals y

Means: A computability equation or relation stating: equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-aa3243680528363a

We={0}W_e = \{ 0 \}

Read as: W sub e equals the singleton set containing zero

Means: A set-valued computability expression stating: W sub e equals the singleton set containing zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-aaa9402664f1a41f

hh

Read as: h

Means: Computability theory notation denoting: h. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

15 occurrences in this chapter

Equation form expr-aae687415b646286

,then, then

Read as: comma then

Means: Computability theory notation denoting: comma then. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ac436cd55e4a99e9

φe(y)≃φdiag(⌜l⌝)(y)≃φ⌜l⌝(⌜l⌝,y)≃l(⌜l⌝,y)≃g(diag(⌜l⌝),y)≃g(e,y),\cfind{e}(y) & \simeq \cfind{\fn{diag}(\gn{l})}(y) \\ & \simeq \cfind{\gn{l}}(\gn{l}, y) \\ & \simeq l(\gn{l}, y) \\ & \simeq g(\fn{diag}(\gn{l}),y) \\ & \simeq g(e, y),

Read as: the partial function at index e on y agrees in definedness and value with the function obtained by diagonalizing the code of l; then with l applied to its own code and y; then with g applied to that diagonal index and y; and finally with g applied to e and y

Means: A source ordered calculation or equivalence chain stating: the partial function at index e on y agrees in definedness and value with the function obtained by diagonalizing the code of l; then with l applied to its own code and y; then with g applied to that diagonal index and y; and finally with g applied to e and y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-acac86c0e609ca90

ll

Read as: l

Means: Computability theory notation denoting: l. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

6 occurrences in this chapter

Equation form expr-af5b9e3beaa7c29f

μyf(x→,y)\umin{y}{f (\vec x, y)}

Read as: the least y such that f open parenthesis vector x comma y close parenthesis

Means: A partial computation or program indexing expression stating: the least y such that f open parenthesis vector x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-b1867ce58a6219b7

n(x)n(x)

Read as: n open parenthesis x close parenthesis

Means: Computability theory notation denoting: n open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b277b7f59890a839

A∩BA \cap B

Read as: A intersect B

Means: Computability theory notation denoting: A intersect B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

8 occurrences in this chapter

Equation form expr-b478c5d487e603b2

We=∅W_e = \emptyset

Read as: W sub e equals the empty set

Means: An index set or many one reducibility expression stating: W sub e equals the empty set. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b4b2e1b50bc0c27b

x∈Kx \in K

Read as: x is in K

Means: A computability equation or relation stating: x is in K. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-b57f80b7826bbc61

h(x,y)≃g(y)h(x,y) \simeq g(y)

Read as: h open parenthesis x comma y close parenthesis has the same definedness and value as g open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: h open parenthesis x comma y close parenthesis has the same definedness and value as g open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b5a1fa433b750c65

φe(y)≃g(e,y)\cfind{e}(y) \simeq g(e,y)

Read as: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as g open parenthesis e comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b5df990524aa6b9a

φe(x)≃U(μsT(e,x,s)).\cfind{e}(x) \simeq U(\umin{s}{T(e, x, s)}).

Read as: partial recursive function phi sub e open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b668ad01671ed051

φe(y)\cfind{e}(y)

Read as: partial recursive function phi sub e open parenthesis y close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b7caa51ec5e32350

f(x)=Un′(k,x)f(x) = \fn{Un}'(k,x)

Read as: f open parenthesis x close parenthesis equals the function Un prime open parenthesis k comma x close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis equals the function Un prime open parenthesis k comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b81e04eb2f66c5e7

φsmn(e,a0,…,am−1)[n](y0,…,yn−1)≃φe[m+n](a0,…,am−1,y0,…,yn−1).\cfind{s^m_n(e, a_0, \dots, a_{m-1})}[n](y_0, \dots, y_{n-1}) \simeq \cfind{e}[m+n](a_0, \dots, a_{m-1}, y_0, \dots, y_{n-1}).

Read as: the n place partial function at the index produced by s superscript m sub n from e and the fixed parameters agrees in definedness and value with the m plus n place partial function at index e on the fixed parameters followed by the remaining inputs

Means: A partial computation or program indexing expression stating: the n place partial function at the index produced by s superscript m sub n from e and the fixed parameters agrees in definedness and value with the m plus n place partial function at index e on the fixed parameters followed by the remaining inputs. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b8e1859ca4fcaa9f

f:ℕ⇀ℕf\colon \Nat \pto \Nat

Read as: f is a partial function from the natural numbers to the natural numbers

Means: Computability theory notation denoting: f is a partial function from the natural numbers to the natural numbers. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b8e2b244c77b7c22

λx.g(xx)\lambd[x][g(xx)]

Read as: lambda x, g applied to x applied to x

Means: A fixed point, diagonalization, or lambda calculus expression stating: lambda x, g applied to x applied to x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b8ea30ff416f888a

⟨(z)0,(z)1⟩\tuple{(z)_0, (z)_1}

Read as: the tuple open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one

Means: Computability theory notation denoting: the tuple open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b9054d2f30d98863

Un′(e,x)≃g(h(e,x),e,x).\fn{Un'}(e,x) \simeq g(h(e,x),e,x).

Read as: the function Un prime open parenthesis e comma x close parenthesis has the same definedness and value as g open parenthesis h open parenthesis e comma x close parenthesis comma e comma x close parenthesis

Means: A partial computation or program indexing expression stating: the function Un prime open parenthesis e comma x close parenthesis has the same definedness and value as g open parenthesis h open parenthesis e comma x close parenthesis comma e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b9101045f11b5953

φdiag(x)(y)≃φx(x,y).\cfind{\fn{diag}(x)}(y) \simeq \cfind{x}(x,y).

Read as: partial recursive function phi sub the function diag open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis x comma y close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: partial recursive function phi sub the function diag open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as partial recursive function phi sub x open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b9c2891680b1b7e4

diag(x)\fn{diag}(x)

Read as: the function diag open parenthesis x close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: the function diag open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b9c7cd1b435de79a

φk[n]\cfind{k}[n]

Read as: partial recursive function phi sub k at arity n

Means: A partial computation or program indexing expression stating: partial recursive function phi sub k at arity n. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-b9d7c18b6334d33d

W0W_0

Read as: W sub zero

Means: An index set or many one reducibility expression stating: W sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ba0b28944edf8cb5

φs(e,x,y)(z)≃φe[3](x,y,z)≃φx(y).\cfind{s(e,x,y)}(z) & \simeq \cfind{e}[3](x,y,z) \\ & \simeq \cfind{x}(y).

Read as: the partial function at index s of e, x, and y on z agrees in definedness and value with the three place partial function at index e on x, y, and z, and then with the partial function at index x on y

Means: A source ordered calculation or equivalence chain stating: the partial function at index s of e, x, and y on z agrees in definedness and value with the three place partial function at index e on x, y, and z, and then with the partial function at index x on y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-bb4be1b56214063c

U((z)1)=yU((z)_1) = y

Read as: U open parenthesis open parenthesis z close parenthesis sub one close parenthesis equals y

Means: A computability equation or relation stating: U open parenthesis open parenthesis z close parenthesis sub one close parenthesis equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-bbe507bd571949d5

A¯\Complement{A}

Read as: the complement of A

Means: An index set or many one reducibility expression stating: the complement of A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

8 occurrences in this chapter

Equation form expr-bd929c799e4369f1

K0={⟨e,x⟩:x∈We}K_0 = \Setabs{\tuple{e,x}}{x \in W_e}

Read as: K sub zero equals the set of the tuple e comma x such that x is in W sub e

Means: An index set or many one reducibility expression stating: K sub zero equals the set of the tuple e comma x such that x is in W sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-be2f33f98a56522c

Un(e,x)≃U(μsT(e,x,s))\fn{Un}(e,x) \simeq U(\umin{s}{T(e,x,s)})

Read as: the universal function open parenthesis e comma x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: the universal function open parenthesis e comma x close parenthesis has the same definedness and value as U open parenthesis the least s such that T open parenthesis e comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-bfae91d5dd7c336c

K={e:φe(e)↓}K = \Setabs{e}{\cfind{e}(e) \fdefined}

Read as: K equals the set of e such that partial recursive function phi sub e open parenthesis e close parenthesis is defined

Means: An index set or many one reducibility expression stating: K equals the set of e such that partial recursive function phi sub e open parenthesis e close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-c0622eaf6294eac5

s(e,x)∈As(e,x) \in A

Read as: s open parenthesis e comma x close parenthesis is in A

Means: A computability equation or relation stating: s open parenthesis e comma x close parenthesis is in A. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c0ae3e3b1eaf0f2f

φdiag(x)(y)≃s(x,y).\cfind{\fn{diag}(x)}(y) \simeq s(x,y).

Read as: partial recursive function phi sub the function diag open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as s open parenthesis x comma y close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: partial recursive function phi sub the function diag open parenthesis x close parenthesis open parenthesis y close parenthesis has the same definedness and value as s open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c20c5153481376ca

Un(k,x)\fn{Un}(k, x)

Read as: the universal function open parenthesis k comma x close parenthesis

Means: A partial computation or program indexing expression stating: the universal function open parenthesis k comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c2c5eeeab86b1b20

g(Yg)g(Yg)

Read as: g applied to Y applied to g

Means: Computability theory notation denoting: g applied to Y applied to g. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-c300eb1abe7dda4a

Un′(k,k)\fn{Un}'(k,k)

Read as: the function Un prime open parenthesis k comma k close parenthesis

Means: A partial computation or program indexing expression stating: the function Un prime open parenthesis k comma k close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c30889161dc8c78d

φe(e)≃{0if h(⌜φe(e)⌝)=0undefinedotherwise,\cfind{e}(e) \simeq \begin{cases} 0 & \text{if $h(\gn{\cfind{e}(e)}) = 0$} \\ \text{undefined} & \text{otherwise,} \end{cases}

Read as: partial recursive function phi sub e open parenthesis e close parenthesis has the same definedness and value as cases begin; row one: zero, if h open parenthesis the Goedel number of partial recursive function phi sub e open parenthesis e close parenthesis close parenthesis equals zero; row two: undefined, otherwise; cases end

Means: A source-ordered partial-function case definition whose second row is undefined otherwise. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c352f833a87addf8

A≤mCA \leq_m C

Read as: A is many one reducible to C

Means: An index set or many one reducibility expression stating: A is many one reducible to C. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c48253f623b68092

y∈Sy \in S

Read as: y is in S

Means: A computability equation or relation stating: y is in S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-c5105d6c5706d855

{0,1}\{ 0, 1 \}

Read as: the set containing zero and one

Means: A set expression denoting the set containing zero and one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c927d43df46020df

fe(x)=Un(e,x)f_e(x) = \fn{Un}(e,x)

Read as: f sub e open parenthesis x close parenthesis equals the universal function open parenthesis e comma x close parenthesis

Means: A partial computation or program indexing expression stating: f sub e open parenthesis x close parenthesis equals the universal function open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-c9307783aa9a4a4d

≤m\le_m

Read as: many one reducibility

Means: Computability theory notation denoting: many one reducibility. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-c9d19e892cdd0f9f

h(x)=μs(T(d,x,s)∨T(e,x,s)).h(x) = \umin{s}{(T(d,x,s) \lor T(e,x,s))}.

Read as: h open parenthesis x close parenthesis equals the least s such that open parenthesis T open parenthesis d comma x comma s close parenthesis or T open parenthesis e comma x comma s close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: h open parenthesis x close parenthesis equals the least s such that open parenthesis T open parenthesis d comma x comma s close parenthesis or T open parenthesis e comma x comma s close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ca978112ca1bbdca

aa

Read as: a

Means: Computability theory notation denoting: a. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-ca9a219723044523

⟨e,x⟩\tuple{e,x}

Read as: the tuple e comma x

Means: Computability theory notation denoting: the tuple e comma x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-cae6ad27ea3ee025

k(x)={f(x/2)if x is eveng((x−1)/2)if x is odd.k(x) = \begin{cases} f(x/2) & \text{if $x$ is even} \\ g((x-1)/2) & \text{if $x$ is odd.} \end{cases}

Read as: k open parenthesis x close parenthesis equals cases begin; row one: f open parenthesis x divided by two close parenthesis, if x is even; row two: g open parenthesis open parenthesis x minus one close parenthesis divided by two close parenthesis, if x is odd; cases end

Means: A source ordered partial or total case definition stating: k open parenthesis x close parenthesis equals cases begin; row one: f open parenthesis x divided by two close parenthesis, if x is even; row two: g open parenthesis open parenthesis x minus one close parenthesis divided by two close parenthesis, if x is odd; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-cbc42bd359f0a11e

μsT(e,x,s)\umin{s}{T(e, x, s)}

Read as: the least s such that T open parenthesis e comma x comma s close parenthesis

Means: A partial computation or program indexing expression stating: the least s such that T open parenthesis e comma x comma s close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-cd0aa9856147b6c5

gg

Read as: g

Means: Computability theory notation denoting: g. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

24 occurrences in this chapter

Equation form expr-cdcaf5fc8a4a048f

d(k)≃φk(k)d(k) \simeq \cfind{k}(k)

Read as: d open parenthesis k close parenthesis has the same definedness and value as partial recursive function phi sub k open parenthesis k close parenthesis

Means: A partial computation or program indexing expression stating: d open parenthesis k close parenthesis has the same definedness and value as partial recursive function phi sub k open parenthesis k close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ce0a7ad973bc52f0

f(x)↑f(x) \fundefined

Read as: f open parenthesis x close parenthesis is undefined

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis is undefined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ce96dd21bc582d4e

φe(y)≃{0if y=0 and φf(e)(0)↓=0undefinedotherwise.\cfind{e}(y) \simeq \begin{cases} 0 & \text{if $y=0$ and $\cfind{f(e)}(0) \fdefined = 0$} \\ \text{undefined} & \text{otherwise.} \end{cases}

Read as: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: zero, if y equals zero and partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis zero close parenthesis is defined and equals zero; row two: undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: partial recursive function phi sub e open parenthesis y close parenthesis has the same definedness and value as cases begin; row one: zero, if y equals zero and partial recursive function phi sub f open parenthesis e close parenthesis open parenthesis zero close parenthesis is defined equals zero; row two: undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-cf5fcf757b255a84

K1K_1

Read as: K sub one

Means: An index set or many one reducibility expression stating: K sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

9 occurrences in this chapter

Equation form expr-cf624dace3fec4da

{x:∀y∀y′((y<y′∧φx(y)↓)∧(φx(y′)↓→φx(y)<φx(y′)))}\Setabs{x}{\lforall[y][\lforall[y'][((y<y' \land \cfind{x}(y)\fdefined) \land (\cfind{x}(y')\fdefined \lif \cfind{x}(y)<\cfind{x}(y')))]]}

Read as: the set of x such that for every y, for every y prime , open parenthesis open parenthesis y is less than y prime and partial recursive function phi sub x open parenthesis y close parenthesis is defined close parenthesis and open parenthesis partial recursive function phi sub x open parenthesis y prime close parenthesis is defined implies partial recursive function phi sub x open parenthesis y close parenthesis is less than partial recursive function phi sub x open parenthesis y prime close parenthesis close parenthesis close parenthesis

Means: An index set or many one reducibility expression stating: the set of x such that for every y, for every y prime , open parenthesis open parenthesis y is less than y prime and partial recursive function phi sub x open parenthesis y close parenthesis is defined close parenthesis and open parenthesis partial recursive function phi sub x open parenthesis y prime close parenthesis is defined implies partial recursive function phi sub x open parenthesis y close parenthesis is less than partial recursive function phi sub x open parenthesis y prime close parenthesis close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-cf7e885b858ad8c6

f(z)=μy(len(z)=2∧T((z)0,(z)1,y)).f(z) = \umin{y}{(\len{z} = 2 \land T((z)_0, (z)_1, y))}.

Read as: f open parenthesis z close parenthesis equals the least y such that open parenthesis the length of z equals two and T open parenthesis open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one comma y close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis z close parenthesis equals the least y such that open parenthesis the length of z equals two and T open parenthesis open parenthesis z close parenthesis sub zero comma open parenthesis z close parenthesis sub one comma y close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d01794b5f0c3ada0

W1W_1

Read as: W sub one

Means: An index set or many one reducibility expression stating: W sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d03502c43d74a30b

,,

Read as: comma

Means: Computability theory notation denoting: comma. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d0861168a7b4742e

φ2\cfind{2}

Read as: partial recursive function phi sub two

Means: A partial computation or program indexing expression stating: partial recursive function phi sub two. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-d09c0982c7627db9

x,yx, y

Read as: x comma y

Means: Computability theory notation denoting: x comma y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d0dac03b0ab83fdf

n=φen = \cfind{e}

Read as: n equals partial recursive function phi sub e

Means: A partial computation or program indexing expression stating: n equals partial recursive function phi sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d0e9583fe4b4c63b

Tot={x:for every y, φx(y)↓}.\fn{Tot} = \Setabs{x}{\text{for every $y$, $\cfind{x}(y)\fdefined$}}.

Read as: Tot equals the set of indices x such that for every y comma partial recursive function phi sub x open parenthesis y close parenthesis is defined

Means: The index-set definition stating that Tot is the set of indices x whose associated partial function is defined for every input y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d2409ab05a08df78

s(e,x,y)∈K1s(e,x,y) \in K_1

Read as: s open parenthesis e comma x comma y close parenthesis is in K sub one

Means: An index set or many one reducibility expression stating: s open parenthesis e comma x comma y close parenthesis is in K sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d2821ca756c57599

f(x)≃Un(e,x)f(x) \simeq \fn{Un}(e,x)

Read as: f open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis e comma x close parenthesis

Means: A partial computation or program indexing expression stating: f open parenthesis x close parenthesis has the same definedness and value as the universal function open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-d2dce5ee489c0cb2

φe(x)↓=y\cfind{e}(x) \fdefined = y

Read as: partial recursive function phi sub e open parenthesis x close parenthesis is defined and equals y

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis is defined equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-d36d8fbbab685971

f=φe[3]f = \cfind{e}[3]

Read as: f equals partial recursive function phi sub e at arity three

Means: A partial computation or program indexing expression stating: f equals partial recursive function phi sub e at arity three. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d40ad6a7c21ffd8b

φs(e,x)\cfind{s(e,x)}

Read as: partial recursive function phi sub s open parenthesis e comma x close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub s open parenthesis e comma x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-d446b7a2d3dfa4b6

m(x)m(x)

Read as: m open parenthesis x close parenthesis

Means: Computability theory notation denoting: m open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d4735e3a265e16ee

22

Read as: two

Means: Computability theory notation denoting: two. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d480126dca43e5e9

φ0\cfind{0}

Read as: partial recursive function phi sub zero

Means: A partial computation or program indexing expression stating: partial recursive function phi sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-d4c39e5e1f0a0028

exe_x

Read as: e sub x

Means: Computability theory notation denoting: e sub x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-d5485e111b51d4c8

K={x:φx(x)↓},K = \Setabs{x}{\cfind{x}(x) \fdefined},

Read as: K equals the set of x such that partial recursive function phi sub x open parenthesis x close parenthesis is defined

Means: An index set or many one reducibility expression stating: K equals the set of x such that partial recursive function phi sub x open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d76c929dee4a1980

φe\cfind{e}

Read as: partial recursive function phi sub e

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

15 occurrences in this chapter

Equation form expr-d7fd0cf2d5e69efb

Y=λg.((λx.g(xx))(λx.g(xx)))Y = \lambd[g][((\lambd[x][g(xx)])(\lambd[x][g(xx)]))]

Read as: Y equals lambda g, the self application of lambda x, g applied to x applied to x

Means: A fixed point, diagonalization, or lambda calculus expression stating: Y equals lambda g, the self application of lambda x, g applied to x applied to x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d813c0d1978a847f

gcd(u,v)≃{vif u=0gcd(mod(v,u),u)otherwise\fn{gcd}(u,v) \simeq \begin{cases} v & \text{if $u = 0$} \\ \fn{gcd}(\fn{mod}(v, u), u) & \text{otherwise} \end{cases}

Read as: the function gcd open parenthesis u comma v close parenthesis has the same definedness and value as cases begin; row one: v, if u equals zero; row two: the function gcd open parenthesis the function mod open parenthesis v comma u close parenthesis comma u close parenthesis, otherwise; cases end

Means: A source ordered partial or total case definition stating: the function gcd open parenthesis u comma v close parenthesis has the same definedness and value as cases begin; row one: v, if u equals zero; row two: the function gcd open parenthesis the function mod open parenthesis v comma u close parenthesis comma u close parenthesis, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-d98041120e41b0a6

g(x)≃{0if h(⌜φx(x)⌝)=0undefinedotherwiseg(x) \simeq \begin{cases} 0 & \text{if $h(\gn{\cfind{x}(x)}) = 0$} \\ \text{undefined} & \text{otherwise} \end{cases}

Read as: g open parenthesis x close parenthesis has the same definedness and value as cases begin; row one: zero, if h open parenthesis the Goedel number of partial recursive function phi sub x open parenthesis x close parenthesis close parenthesis equals zero; row two: undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: g open parenthesis x close parenthesis has the same definedness and value as cases begin; row one: zero, if h open parenthesis the Goedel number of partial recursive function phi sub x open parenthesis x close parenthesis close parenthesis equals zero; row two: undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-da7ac8485359871b

g(y)=μx(f(x)=y).g(y) = \umin{x}{(f(x) = y)}.

Read as: g open parenthesis y close parenthesis equals the least x such that open parenthesis f open parenthesis x close parenthesis equals y close parenthesis

Means: A partial computation or program indexing expression stating: g open parenthesis y close parenthesis equals the least x such that open parenthesis f open parenthesis x close parenthesis equals y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-daa35700f4bd10c2

diag\fn{diag}

Read as: the function diag

Means: A fixed point, diagonalization, or lambda calculus expression stating: the function diag. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

6 occurrences in this chapter

Equation form expr-daeccc074caf3d48

K0¯\Complement{K_0}

Read as: the complement of K sub zero

Means: An index set or many one reducibility expression stating: the complement of K sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-dcdf8b93520408f3

y0y_0

Read as: y sub zero

Means: Computability theory notation denoting: y sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-dd5e51cc9a7a7fcb

Un′\fn{Un'}

Read as: the function Un prime

Means: Computability theory notation denoting: the function Un prime. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-de0d1f3bbb31c87f

{0}\{ 0 \}

Read as: the singleton set containing zero

Means: A set expression denoting the singleton set containing zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-def9261af216c3fb

R(x,y)R(x,y)

Read as: R open parenthesis x comma y close parenthesis

Means: Computability theory notation denoting: R open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-df70a762b6a56203

Un(e,e)\fn{Un}(e, e)

Read as: the universal function open parenthesis e comma e close parenthesis

Means: A partial computation or program indexing expression stating: the universal function open parenthesis e comma e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-df7e70e5021544f4

BB

Read as: B

Means: Computability theory notation denoting: B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

40 occurrences in this chapter

Equation form expr-dfebe77783f5f65e

K={x:x∈Wx}K = \Setabs{x}{x \in W_x}

Read as: K equals the set of x such that x is in W sub x

Means: An index set or many one reducibility expression stating: K equals the set of x such that x is in W sub x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e04a9884677b59c7

x∈Aif and only iff(x)∈B.x \in A \quad \text{if and only if} \quad f(x) \in B.

Read as: x is in A if and only if f open parenthesis x close parenthesis is in B

Means: A computability equation or relation stating: x is in A if and only if f open parenthesis x close parenthesis is in B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e2d1e935405a4622

B≤mCB \leq_m C

Read as: B is many one reducible to C

Means: An index set or many one reducibility expression stating: B is many one reducible to C. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e314afc8fa785187

x=kx = k

Read as: x equals k

Means: A computability equation or relation stating: x equals k. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e3160dc705af73e1

φx(x)\cfind{x}(x)

Read as: partial recursive function phi sub x open parenthesis x close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub x open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-e632b7095b0bf32c

TT

Read as: T

Means: Computability theory notation denoting: T. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

7 occurrences in this chapter

Equation form expr-e6c4e422217d9f6e

F(F)=0F(F) = 0

Read as: F open parenthesis F close parenthesis equals zero

Means: A computability equation or relation stating: F open parenthesis F close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e6e7c761513e3107

S={f(0),f(1),f(2),…},S = \{ f(0), f(1), f(2), \dots \},

Read as: S equals the set containing f open parenthesis zero close parenthesis comma f open parenthesis one close parenthesis comma f open parenthesis two close parenthesis comma and so on

Means: A set-valued computability expression stating: S equals the set containing f open parenthesis zero close parenthesis comma f open parenthesis one close parenthesis comma f open parenthesis two close parenthesis comma and so on. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e749ab67eab0ef3d

s(e,x,y)s(e,x,y)

Read as: s open parenthesis e comma x comma y close parenthesis

Means: Computability theory notation denoting: s open parenthesis e comma x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-e7d953b466c7b4be

F(f)={1if f is in the domain of f, and f(f)=00otherwiseF(f) = \begin{cases} 1 & \text{if $f$ is in the domain of $f$, and $f(f) = 0$} \\ 0 & \text{otherwise} \end{cases}

Read as: F open parenthesis f close parenthesis equals cases begin; row one: one, if f is in the domain of f comma and f open parenthesis f close parenthesis equals zero; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: F open parenthesis f close parenthesis equals cases begin; row one: one, if f is in the domain of f comma and f open parenthesis f close parenthesis equals zero; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e8219069833d2f8e

φe(x)↓\cfind{e}(x) \fdefined

Read as: partial recursive function phi sub e open parenthesis x close parenthesis is defined

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis x close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-e8ad50fad563fa23

B¯\Complement{B}

Read as: the complement of B

Means: An index set or many one reducibility expression stating: the complement of B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

3 occurrences in this chapter

Equation form expr-e8c17252cf9632d5

χR\Char{R}

Read as: the characteristic function of R

Means: A computable relation or logical condition stating: the characteristic function of R. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-e92cff78afc60941

h(x,y)≃{0if x∈K↑otherwiseh(x,y) \simeq \begin{cases} 0 & \text{if $x \in K$} \\ \fundefined & \text{otherwise} \end{cases}

Read as: h open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: zero, if x is in K; row two: is undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: h open parenthesis x comma y close parenthesis has the same definedness and value as cases begin; row one: zero, if x is in K; row two: is undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ead977e0bd2faddb

f(x)=⟨e,x⟩f(x) = \tuple{e, x}

Read as: f open parenthesis x close parenthesis equals the tuple e comma x

Means: A computability equation or relation stating: f open parenthesis x close parenthesis equals the tuple e comma x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ec0a2418960e419c

S=WeS = W_e

Read as: S equals W sub e

Means: An index set or many one reducibility expression stating: S equals W sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ee02dc8e71f7a0d0

S={x:∃yT(e,x,y)}.S = \Setabs{ x }{ \lexists[y][T(e, x, y)] }.

Read as: S equals the set of x such that there exists y, T open parenthesis e comma x comma y close parenthesis

Means: An index set or many one reducibility expression stating: S equals the set of x such that there exists y, T open parenthesis e comma x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ef0cbbf006d7c1e4

⌜φx(y)⌝\gn{\cfind{x}(y)}

Read as: the Goedel number of partial recursive function phi sub x open parenthesis y close parenthesis

Means: A fixed point, diagonalization, or lambda calculus expression stating: the Goedel number of partial recursive function phi sub x open parenthesis y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ef21b41b5dd52956

φe(e)\cfind{e}(e)

Read as: partial recursive function phi sub e open parenthesis e close parenthesis

Means: A partial computation or program indexing expression stating: partial recursive function phi sub e open parenthesis e close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Equation form expr-ef2d127de37b942b

55

Read as: five

Means: Computability theory notation denoting: five. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f14ec4fb4b109c26

print\fn{print}

Read as: the function print

Means: Computability theory notation denoting: the function print. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f172ad0aae8c01eb

S∉SS \notin S

Read as: S is not in S

Means: A computability equation or relation stating: S is not in S. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f3b171aca27f5a05

k(x)k(x)

Read as: k open parenthesis x close parenthesis

Means: Computability theory notation denoting: k open parenthesis x close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f3c143179694d5bc

K0K_0

Read as: K sub zero

Means: An index set or many one reducibility expression stating: K sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

26 occurrences in this chapter

Equation form expr-f3f3804480e8551a

β\beta

Read as: beta

Means: Computability theory notation denoting: beta. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f4520b4c474518ab

S={y:for some x, f(x)=y}.S = \Setabs{y}{\text{for some $x$, } f(x) = y}.

Read as: S equals the set of y such that for some x comma f open parenthesis x close parenthesis equals y

Means: An index set or many one reducibility expression stating: S equals the set of y such that for some x comma f open parenthesis x close parenthesis equals y. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f58d7220499e2505

K1={e:φe(0)↓}.K_1 = \Setabs{e}{\cfind{e}(0) \fdefined}.

Read as: K sub one equals the set of e such that partial recursive function phi sub e open parenthesis zero close parenthesis is defined

Means: An index set or many one reducibility expression stating: K sub one equals the set of e such that partial recursive function phi sub e open parenthesis zero close parenthesis is defined. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f67ab10ad4e4c531

FF

Read as: F

Means: Computability theory notation denoting: F. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

4 occurrences in this chapter

Equation form expr-f68b21b6d1cb90fe

d(e)={1if χK(e)=0↑otherwise.d(e) = \begin{cases} 1 & \text{if\/ $\Char{K}(e) = 0$}\\ \fundefined & \text{otherwise.} \end{cases}

Read as: d open parenthesis e close parenthesis equals cases begin; row one: one, if the characteristic function of K open parenthesis e close parenthesis equals zero; row two: is undefined, otherwise; cases end

Means: A source ordered partial or total case definition stating: d open parenthesis e close parenthesis equals cases begin; row one: one, if the characteristic function of K open parenthesis e close parenthesis equals zero; row two: is undefined, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f7cf8bc2175c06dd

,andif, and if

Read as: comma and if

Means: Computability theory notation denoting: comma and if. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f90732290a72c769

Un′(e,x)={Un(e,x)if h(e,x)=10otherwise.\fn{Un'}(e,x) = \begin{cases} \fn{Un}(e,x) & \text{if $h(e,x) = 1$} \\ 0 & \text{otherwise.} \end{cases}

Read as: the function Un prime open parenthesis e comma x close parenthesis equals cases begin; row one: the universal function open parenthesis e comma x close parenthesis, if h open parenthesis e comma x close parenthesis equals one; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: the function Un prime open parenthesis e comma x close parenthesis equals cases begin; row one: the universal function open parenthesis e comma x close parenthesis, if h open parenthesis e comma x close parenthesis equals one; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f9383901eebb1eca

diag(x)=xx\fn{diag}(x) = xx

Read as: diag of x equals x applied to x

Means: A fixed point, diagonalization, or lambda calculus expression stating: diag of x equals x applied to x. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f9b69eb01778ee91

S={x:∃yR(x,y)}S = \Setabs{ x }{ \lexists[y][R(x, y)] }

Read as: S equals the set of x such that there exists y, R open parenthesis x comma y close parenthesis

Means: An index set or many one reducibility expression stating: S equals the set of x such that there exists y, R open parenthesis x comma y close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-f9e012396be65db0

llll

Read as: l applied to l

Means: Computability theory notation denoting: l applied to l. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fa09799b67f8f537

A=WeA = W_e

Read as: A equals W sub e

Means: An index set or many one reducibility expression stating: A equals W sub e. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-faba6da82607bd53

h(e,x)={1if Un(e,x) is defined0otherwise.h(e, x) = \begin{cases} 1 & \text{if\/ $\fn{Un}(e, x)$ is defined} \\ 0 & \text{otherwise.} \end{cases}

Read as: h open parenthesis e comma x close parenthesis equals cases begin; row one: one, if the universal function open parenthesis e comma x close parenthesis is defined; row two: zero, otherwise; cases end

Means: A source ordered partial or total case definition stating: h open parenthesis e comma x close parenthesis equals cases begin; row one: one, if the universal function open parenthesis e comma x close parenthesis is defined; row two: zero, otherwise; cases end. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fb01c0abe41d4a5d

χB\Char{B}

Read as: the characteristic function of B

Means: A computable relation or logical condition stating: the characteristic function of B. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fb4b2bf42e61ccfe

Tot\fn{Tot}

Read as: the set Tot

Means: An index-set expression denoting the set Tot. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

6 occurrences in this chapter

Equation form expr-fca77de57b28ac96

f(x)∈K0f(x) \in K_0

Read as: f open parenthesis x close parenthesis is in K sub zero

Means: An index set or many one reducibility expression stating: f open parenthesis x close parenthesis is in K sub zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fcf8ad218106c897

d(k)d(k)

Read as: d open parenthesis k close parenthesis

Means: Computability theory notation denoting: d open parenthesis k close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fd15e3089f2a7e5b

f(2)f(2)

Read as: f open parenthesis two close parenthesis

Means: Computability theory notation denoting: f open parenthesis two close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fd6c580d42194f41

f(x)=0f(x) = 0

Read as: f open parenthesis x close parenthesis equals zero

Means: A computability equation or relation stating: f open parenthesis x close parenthesis equals zero. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-fe335307a56dc6ba

isintherangeofis in the range of

Read as: is in the range of

Means: Computability theory notation denoting: is in the range of. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ff971a3787400ba5

p(x)=μy(T(d,x,y)∨T(e,x,y)).p(x) = \umin{y}{(T(d,x,y) \lor T(e,x,y))}.

Read as: p open parenthesis x close parenthesis equals the least y such that open parenthesis T open parenthesis d comma x comma y close parenthesis or T open parenthesis e comma x comma y close parenthesis close parenthesis

Means: A partial computation or program indexing expression stating: p open parenthesis x close parenthesis equals the least y such that open parenthesis T open parenthesis d comma x comma y close parenthesis or T open parenthesis e comma x comma y close parenthesis close parenthesis. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

1 occurrence in this chapter

Equation form expr-ffebbdd908d3c44d

φ1\cfind{1}

Read as: partial recursive function phi sub one

Means: A partial computation or program indexing expression stating: partial recursive function phi sub one. This meaning was freshly adjudicated against every exact Computability Theory occurrence rather than imported from a prior tranche.

2 occurrences in this chapter

Kleene normal form theorem

The theorem states that fixed primitive recursive objects T and U represent every partial computable function. For a suitable index e, the value at x is obtained by finding the least computation code s accepted by T and applying U to that code, with the same definedness and value as the original function.

Source

Infinitely many indices theorem

The theorem states that every partial computable function is represented by infinitely many distinct program indices.

Source

Parameterization theorem

For each pair of arities n and m, the theorem supplies a primitive recursive parameterization function. It fixes the first m arguments of a program with index e and returns an index for the resulting n place partial computable function, preserving the same definedness and value on all remaining inputs.

Source

Universal partial computable function theorem

The theorem states that there is one partial computable function Un of an index and an input that enumerates all partial computable unary functions. Every such function agrees in definedness and value with Un at some fixed index on every input.

Source

No universal total computable function theorem

The theorem states that no computable function can enumerate all total computable unary functions by an index parameter. Any function having that claimed universal property must itself fail to be computable.

Source

Partial diagonalization exercise

Question only; no solution is supplied. It asks why the diagonal argument against a universal total computable function does not also refute the universal partial computable function, by examining the partial function obtained from the diagonal value of Un plus one.

Source

Halting function theorem

The theorem defines h to return one when the universal computation with program e and input x is defined and zero otherwise, then states that h is not computable.

Source

Halting proof recursion display

The first row gives g at stage zero as zero. The second row gives g at every positive successor stage as the universal partial computation with index e on input x. The display is the recursive construction used in the halting proof.

Source

Definition of computable sets and relations

The definition calls a set computable exactly when its characteristic function is computable. The displayed characteristic function returns one for members of the set and zero otherwise. It extends the same criterion to relations and notes that computable sets and relations are also called decidable.

Source

Definition of computably enumerable sets

The definition calls a set computably enumerable when it is empty or is the range of a computable function.

Source

Equivalent definitions of computably enumerable sets theorem

The theorem states four equivalent conditions for a set S. It is computably enumerable, it is the range of a partial computable function, it is empty or the range of a primitive recursive function, and it is the domain of a partial computable function.

Source

Existential characterization theorem

The theorem states that a set S is computably enumerable exactly when membership in S can be expressed by the existence of a natural number y satisfying a computable relation R of x and y.

Source

Paired halting set theorem

The theorem defines K zero as the set of pairs consisting of an index e and an input x for which the corresponding partial computation is defined. It states that K zero is computably enumerable but not computable.

Source

Self halting set theorem

The theorem defines K as the set of indices whose corresponding partial computation is defined on its own index. It states that K is computably enumerable but not decidable.

Source

Closure under union and intersection theorem

The theorem states that the union and the intersection of any two computably enumerable sets are again computably enumerable.

Source

Union and intersection searches display

The first row defines h of x as the least stage at which either enumerating function produces x. The second row defines j of x as the least coded pair of stages at which both enumerating functions produce x. These searches witness closure under union and intersection.

Source

Complement characterization theorem

The theorem states that a set A is computable exactly when both A and its complement are computably enumerable.

Source

Complement of paired halting set corollary

The corollary states that the complement of K zero is not computably enumerable.

Source

Definition of many one reducibility

The definition says that a computable function f reduces A to B when x belongs to A exactly when f of x belongs to B. It names this many one reducibility, introduces its notation, and calls two sets many one equivalent when each reduces to the other.

Source

Transitivity of many one reducibility proposition

The proposition states that if A is many one reducible to B and B is many one reducible to C, then A is many one reducible to C.

Source

Transitivity proof exercise

Question only; no solution is supplied. It asks the reader to prove transitivity by composing a reduction from A to B with a reduction from B to C in the source convention for composition.

Source

Reduction preservation proposition

The proposition assumes that A is many one reducible to B. It states that computable enumerability of B implies computable enumerability of A, and computability of B implies computability of A.

Source

Reduction domain equivalence display

The first row says that x belongs to A exactly when f of x belongs to B. The second row says this is equivalent to the partial semidecision procedure g being defined at f of x.

Source

Complement reduction exercise

Question only; no solution is supplied. It asks the reader to show that a many one reduction from A to B is also a many one reduction from the complement of A to the complement of B.

Source

Characteristic function composition exercise

Question only; no solution is supplied. It asks the reader to express the characteristic function of A by composing a reduction from A to B with the characteristic function of B.

Source

Definition of complete computably enumerable sets

The definition calls a set A complete among computably enumerable sets when A is computably enumerable and every computably enumerable set B is many one reducible to A.

Source

Completeness of the canonical halting sets theorem

The theorem states that K, K zero, and K one are all complete computably enumerable sets under many one reducibility.

Source

Reduction from self halting to paired halting exercise

Question only; no solution is supplied. It asks the reader to give a many one reduction from K to K zero.

Source

Zero input halting set proposition

The proposition defines K one as the set of indices whose corresponding partial computation is defined on input zero. It states that K one is computably enumerable but not computable.

Source

Parameterization reduction chain display

The first row gives the partial function indexed by s of e, x, and y on input z as the three place partial function indexed by e at x, y, and z. The second row identifies this with the computation indexed by x on input y, independently of z.

Source

Undecidability of totality proposition

The proposition states that the set Tot of indices of total computable functions is not computable.

Source

Rice theorem

The theorem considers the set A of indices whose partial computable functions belong to a class C. It states that if A is computable, then C must be empty or must contain every partial computable function. Thus every nontrivial extensional property of partial computable functions has an undecidable index set.

Source

Rice theorem examples corollary

The corollary states that four index sets are undecidable. They concern functions whose range contains seventeen, functions that are constant, functions that are total, and functions whose defined values strictly increase with the input. The reader formulas rejoin source expressions split by nested dollar delimiters while retaining the exact source fragments separately.

Source

Fixed point equivalence lemma

The lemma states two equivalent fixed point principles. Every partial computable function g of an index and an input has an index e whose function agrees with g at e, and every computable transformation f of indices has an index e whose function agrees with the function at index f of e.

Source

First fixed point implication display

The corrected reader chain says that the partial function at index e agrees in definedness and value first with the universal function at index f of e and then with the partial function at index f of e.

Source

Second fixed point implication display

The corrected reader chain says that the partial function at index e agrees in definedness and value first with the partial function at index f of e and then with g of e and y.

Source

Computability fixed point theorem

The theorem asserts the equivalent principles from the preceding lemma. In particular, every partial computable function g of an index and an input has an index e whose partial function agrees with g at e on every input.

Source

Fixed point construction chain display

The source ordered chain begins with the partial function at the constructed index e. It passes through diagonalization of the code of l, self application of l to its own code, and application of g to that diagonal index, ending with g of e and y. Every step has the same definedness and value.

Source

Lambda calculus fixed point reduction display

The first row defines k by self application of the lambda term taking x to g applied to x applied to x. The second row beta reduces this term to g applied to the same self application. The last row identifies the result as g applied to k.

Source

No uniform characteristic index selector theorem

The theorem states that no partial computable function f can always take an index e for a computable set W sub e and return a defined index for its characteristic function.

Source

Cross-reference reference-000565

Universal function proof reference to normal form

Source occurrence

Cross-reference reference-000566

Diagonalization explanation reference to universality

Source occurrence

Cross-reference reference-000567

Partial diagonalization exercise reference

Source occurrence

Cross-reference reference-000568

Halting proof contradiction reference

Source occurrence

Cross-reference reference-000569

Primitive range clause implication source

Source occurrence

Cross-reference reference-000570

Primitive range implication destination

Source occurrence

Cross-reference reference-000571

Partial range implication source

Source occurrence

Cross-reference reference-000572

Partial range implication destination

Source occurrence

Cross-reference reference-000573

Primitive range return implication source

Source occurrence

Cross-reference reference-000574

Primitive range return implication destination

Source occurrence

Cross-reference reference-000575

Equivalent definitions proof resumption reference

Source occurrence

Cross-reference reference-000576

Range and domain equivalence first clause reference

Source occurrence

Cross-reference reference-000577

Range and domain equivalence second clause reference

Source occurrence

Cross-reference reference-000578

Range to domain implication source

Source occurrence

Cross-reference reference-000579

Range to domain implication destination

Source occurrence

Cross-reference reference-000580

Domain to range implication source

Source occurrence

Cross-reference reference-000581

Domain to range implication destination

Source occurrence

Cross-reference reference-000582

Domain clause enumeration reference

Source occurrence

Cross-reference reference-000583

Enumeration consequence theorem reference

Source occurrence

Cross-reference reference-000584

Paired halting set undecidability reference

Source occurrence

Cross-reference reference-000585

Closure proof characterization reference

Source occurrence

Cross-reference reference-000586

Complement corollary characterization reference

Source occurrence

Cross-reference reference-000587

Complement corollary halting set reference

Source occurrence

Cross-reference reference-000588

Reducibility introduction halting reference

Source occurrence

Cross-reference reference-000589

Transitivity exercise proposition reference

Source occurrence

Cross-reference reference-000590

Reduction proof complement premise reference

Source occurrence

Cross-reference reference-000591

Reduction proof complement conclusion reference

Source occurrence

Cross-reference reference-000592

Complement nonreducibility corollary reference

Source occurrence

Cross-reference reference-000593

Completeness proof zero input set reference

Source occurrence

Cross-reference reference-000594

Completeness proof transitivity reference

Source occurrence

Cross-reference reference-000595

Zero input set reduction proposition reference

Source occurrence

Cross-reference reference-000596

Zero input set existential characterization reference

Source occurrence

Cross-reference reference-000597

Rice theorem motivation totality reference

Source occurrence

Cross-reference reference-000598

Fixed point equivalence discussion reference

Source occurrence

Cross-reference reference-000599

Fixed point theorem statement reference

Source occurrence

Source disclosures