- #1

Physicist248

- 14

- 4

- TL;DR Summary
- THEOREM 1: There are numbers k and s and a program A(n,m) satisfying the following conditions.

1. If A(n,m)↓, then Cn(m)↑.

2. For all n, C_k(n) = A(n,n) and C_s(n) = C_k(s).

3. A(k,s)↓ and for all n, A(s,n)↑.

Here C_n(∙) is a program with index n in some exhaustive enumeration of all possible programs.

I am proposing a new theorem of computability theory:

THEOREM 1: There are numbers k and s and a program A(n,m) satisfying the following conditions.

1. If A(n,m)↓, then C_n(m)↑.

2. For all n, C_k(n) = A(n,n) and C_s(n) = C_k(s).

3. A(k,s)↓ and for all n, A(s,n)↑.

Here C_n(∙) is a program with index n in some exhaustive enumeration of all possible programs.

PROOF: Let K denote the halting problem, that is, K = {e : C_e(e) ↓}. It is known that the complement of K, ~K, is productive and therefore contains an infinite recursively enumerable (r.e.) subset. Let f be a recursive function such that f(0), f(1), f(2), . . . is a one-one enumeration of an infinite r.e. subset of ~K.

Define a partial-recursive function A(x,y), and numbers k, s such that for all n

⎧ 1 (one) if ∃n(x = y = f(n)) ∨ (x = k & y = s);

A(x,y) = ⎨

⎩ ↑ (diverges) otherwise.

⎧ 1 if A(x,x) = 1

C_k(x) = ⎨

⎩ ↑ otherwise.

By the Recursion Theorem, there are infinitely many s’ such that for all y, C_s’(y) = C_k(s’). Fix one such s’, say s, such that s ≠ k. Choose f(n) with the property that no k’ such that C_k’ = C_k and no s’ such that C_s’(y) = C_k(s’) are in its range. The function f enumerates many functions that do not halt on their own input (hopefully all of them except the equivalents of k and s.)

We may now verify Conditions 1, 2 and 3 as follows.

Condition 1: By the definition of A, A(x,y)↓ only if one of the following holds: (a) x = y = f(n), or (b) (x = k & y = s). In case (a), one has by the definition of f that f(n) ∈ K, that is, C_f(n)(f(n))↑. In case (b), since s has been chosen such that s≠ k, by the definition of C_k(x), Ck(x)↑ if x≠ y.

Condition 2: For all n, C_k(n) = A(n,n) is immediate by the definition of C_k. Furthermore, by the choice of s, for all y, C_s(y) = C_k(s).

Condition 3: Since f was chosen such that for all n, s ≠ f(n), it follows from the definition of A that A(k,s)↓= 1 and for all y, A(s,y)↑. QED

Is this proof correct? Thx.

THEOREM 1: There are numbers k and s and a program A(n,m) satisfying the following conditions.

1. If A(n,m)↓, then C_n(m)↑.

2. For all n, C_k(n) = A(n,n) and C_s(n) = C_k(s).

3. A(k,s)↓ and for all n, A(s,n)↑.

Here C_n(∙) is a program with index n in some exhaustive enumeration of all possible programs.

PROOF: Let K denote the halting problem, that is, K = {e : C_e(e) ↓}. It is known that the complement of K, ~K, is productive and therefore contains an infinite recursively enumerable (r.e.) subset. Let f be a recursive function such that f(0), f(1), f(2), . . . is a one-one enumeration of an infinite r.e. subset of ~K.

Define a partial-recursive function A(x,y), and numbers k, s such that for all n

⎧ 1 (one) if ∃n(x = y = f(n)) ∨ (x = k & y = s);

A(x,y) = ⎨

⎩ ↑ (diverges) otherwise.

⎧ 1 if A(x,x) = 1

C_k(x) = ⎨

⎩ ↑ otherwise.

By the Recursion Theorem, there are infinitely many s’ such that for all y, C_s’(y) = C_k(s’). Fix one such s’, say s, such that s ≠ k. Choose f(n) with the property that no k’ such that C_k’ = C_k and no s’ such that C_s’(y) = C_k(s’) are in its range. The function f enumerates many functions that do not halt on their own input (hopefully all of them except the equivalents of k and s.)

We may now verify Conditions 1, 2 and 3 as follows.

Condition 1: By the definition of A, A(x,y)↓ only if one of the following holds: (a) x = y = f(n), or (b) (x = k & y = s). In case (a), one has by the definition of f that f(n) ∈ K, that is, C_f(n)(f(n))↑. In case (b), since s has been chosen such that s≠ k, by the definition of C_k(x), Ck(x)↑ if x≠ y.

Condition 2: For all n, C_k(n) = A(n,n) is immediate by the definition of C_k. Furthermore, by the choice of s, for all y, C_s(y) = C_k(s).

Condition 3: Since f was chosen such that for all n, s ≠ f(n), it follows from the definition of A that A(k,s)↓= 1 and for all y, A(s,y)↑. QED

Is this proof correct? Thx.