The Permitting Method

233 Views Asked by At

Define the term late permitting in the following way: $C$ late permits an element $x$ to enter $A_{s+1}$ if for a fixed computable function $f$ with $f(n)>n$, there exists $y\leq x$ such that $y\in C_{f(s)}-C_{s}$. In other words, $C$ permits $x$ to enter $A$, but it may take a while to give its permission.

Suppose $C$ late permits each element of $A$ for some enumeration of $A$ and some computable function $f$. Then, how can I prove that $$A\leq_{T}C$$

Additionally, I need to show that there is some other enumeration $\{A_{s}^{*}\}$ of $A$ such that $C$ permits on $A$ in the usual way: i.e., if $x\in A_{s+1}^{*}-A_{s}^{*}$ then there exists $y\leq x$ such that $y\in C_{s+1}-C_{s}$. Note this means that late permitting doesn't give us anything that regular permitting can't.


Definitions and notation:

$A\leq_{T}C$ means $A$ is Turing reducible to $C$

Relevant Theorem: For any noncomputable c.e set $C$ there is a simple set $A\leq_{T}C$.

$(\exists y\leq x)[y\in C_{s+1}-C_{s}]$, i.e., $C$ permits $x$ at state $s+1$

1

There are 1 best solutions below

0
On BEST ANSWER

By enumeration, I assume you always mean computable enumeration.

Suppose $C$ "late permits" $A$. Let $A_s$ be a computable enumeration of $A$, $C_s$ be a enumeration of $C$ and $f$ be a computable function that satisfies the definition of "late permitting".

To show $A \leq_T C$, one wants to show that given an oracle for $C$, one can compute the membership relation $x \in A$. With the oracle for $C$, you can find all the $y \leq x$ such that $y \in C$. Suppose $y_1, ..., y_n$ are all the $y$'s with this property. Since each $y_i \in C$, there exists a smallest $t_i$ such that $y_i \in C_{t_i}$.

Finally $x \in A$ if and only if there exists a $1 \leq i \leq n$ such that there exists a $s < t_i$ such that $y_i \in C_{f(s)}$

It has been shown that $A \leq_T C$.

I will assume that computable enumerations allow possible more than one element to enter at any stage. Another usual convention is that at any stage, if $x \in A_s$, then $x \leq s$.

Define a computable enumeration $A_s^*$ as follows:

$A_0^* = \emptyset$

$x \in A^*_{s + 1}$ if and only if $x \leq s$ and there exists a $t \leq s$ such that there exists a $y \leq x$ such that $y \in C_{f(t)} - C_t$ and the least $u$ such that $t \leq u < f(t)$ and $y \in C_{u + 1} - C_u$ is less than $s$.


Perhaps a little bit easier to understand:

$A_0^* = \emptyset$

$x \in A^*_{s + 1}$ if and only if $x \in A_s^*$ or $x \leq s$ and there exists a $t \leq s$ such that there exists a $y \leq x$ such that $y \in C_{f(t)} - C_t$ and the least $u$ such that $t \leq u < f(t)$ and $y \in C_{u + 1} - C_u$ is $s$.


It is clear that $A_s^*$ is computable. $A_{s}^* \subseteq A_{s+1}^*$. By definition, if $x \in A_{s + 1}^* - A_s^*$, then $x \in C_{s + 1} - C_s$. To show that this new enumeration actually enumerates all of $A$. Suppose $a \in A$. Then there exists a $v$ such that (in the original enumeration), $x$ enters $A_{v + 1} - A_v$. This means that there is some $y < x$ such that $y \in C_{f(v)} - C_v$. There exists a least $u$ between $v$ and $f(v)$ such that $y \in C_{u + 1} - C_u$. Then $x \in A_u^*$.

$A_s^*$ is a computable enumeration of $A$ that permits in the usual sense with respect to the enumeration of $C$.