Is it possible to construct a model of oracle Turing machines that correspond to $omega_n^text{CK}$, where...












2












$begingroup$


I have found the following quotes. Quote $1$ ( source ):




In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($omega_1^text{CK}$). In googology, BB oracles correspond to $ omega_1^text{CK} times 2 $ to the FGH.




(note that “BB oracles” here denote the oracles that can compute the Busy Beaver function for the lower-order Turing machines).



Quote $2$ ( source ):




With access to the halting oracle, you still cannot compute ordinals greater than $ omega_1^text{CK} $. The set of computable ordinals is, in fact, still the same. However, given an oracle for $ omega_1^text{CK} $, we can compute larger ordinals, and in fact the ordinals computable from $ omega_1^text{CK} $ are exactly the ones below $ omega_2^text{CK} $.




(in this quote, I don’t understand what “an oracle for $omega_1^text{CK}$” means).



Quote $3$ ( source ):




Adam Goucher admited he was wrong when he first wrote about strength of $Sigma_2(n)$. It is actually $omega_2^{CK}$, well over $omega_1^{CK} times 2$.




(note that $Sigma_2(n)$ here denotes the Busy Beaver function for the second-order oracle Turing machines, that is, Turing machines equipped with an oracle that can compute the Busy Beaver function for the first-order Turing machines).



It seems like Quote $3$ contradicts Quote $1$, and the question is: is it possible (if yes, then how?) to construct a model of Turing machines that correspond to $ omega_n^text{CK} $ in computability theory, assuming that $n$ can be extended to any natural number greater than $1$? What function would the oracles of such machines compute?



EDIT



Quote $4$ ( source ):




The first two admissible ordinals are ω and $omega _{1}^{mathrm {CK} }$ (the least non-recursive ordinal, also called the Church–Kleene ordinal). Any regular uncountable cardinal is an admissible ordinal.



By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.




Can anyone explain how exactly such construction is done? I cannot find any accessible explanation online.



There are relatively similar questions, but they do not address the described problem:





  • Is there a second Church-Kleene ordinal?

  • What classification of countable ordinals above $omega _{1}^{mathrm {CK} }$ exists?






logic ordinals turing-machines oracles







share|cite|improve this question











$endgroup$












  • $begingroup$
    Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:25










  • $begingroup$
    Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:27










  • $begingroup$
    Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:53










  • $begingroup$
    @Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
    $endgroup$
    – lyrically wicked
    Sep 4 '18 at 8:29










  • $begingroup$
    @Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
    $endgroup$
    – SSequence
    Sep 6 '18 at 9:23


















2












$begingroup$


I have found the following quotes. Quote $1$ ( source ):




In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($omega_1^text{CK}$). In googology, BB oracles correspond to $ omega_1^text{CK} times 2 $ to the FGH.




(note that “BB oracles” here denote the oracles that can compute the Busy Beaver function for the lower-order Turing machines).



Quote $2$ ( source ):




With access to the halting oracle, you still cannot compute ordinals greater than $ omega_1^text{CK} $. The set of computable ordinals is, in fact, still the same. However, given an oracle for $ omega_1^text{CK} $, we can compute larger ordinals, and in fact the ordinals computable from $ omega_1^text{CK} $ are exactly the ones below $ omega_2^text{CK} $.




(in this quote, I don’t understand what “an oracle for $omega_1^text{CK}$” means).



Quote $3$ ( source ):




Adam Goucher admited he was wrong when he first wrote about strength of $Sigma_2(n)$. It is actually $omega_2^{CK}$, well over $omega_1^{CK} times 2$.




(note that $Sigma_2(n)$ here denotes the Busy Beaver function for the second-order oracle Turing machines, that is, Turing machines equipped with an oracle that can compute the Busy Beaver function for the first-order Turing machines).



It seems like Quote $3$ contradicts Quote $1$, and the question is: is it possible (if yes, then how?) to construct a model of Turing machines that correspond to $ omega_n^text{CK} $ in computability theory, assuming that $n$ can be extended to any natural number greater than $1$? What function would the oracles of such machines compute?



EDIT



Quote $4$ ( source ):




The first two admissible ordinals are ω and $omega _{1}^{mathrm {CK} }$ (the least non-recursive ordinal, also called the Church–Kleene ordinal). Any regular uncountable cardinal is an admissible ordinal.



By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.




Can anyone explain how exactly such construction is done? I cannot find any accessible explanation online.



There are relatively similar questions, but they do not address the described problem:





  • Is there a second Church-Kleene ordinal?

  • What classification of countable ordinals above $omega _{1}^{mathrm {CK} }$ exists?






logic ordinals turing-machines oracles







share|cite|improve this question











$endgroup$












  • $begingroup$
    Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:25










  • $begingroup$
    Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:27










  • $begingroup$
    Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:53










  • $begingroup$
    @Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
    $endgroup$
    – lyrically wicked
    Sep 4 '18 at 8:29










  • $begingroup$
    @Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
    $endgroup$
    – SSequence
    Sep 6 '18 at 9:23
















2












2








2


1



$begingroup$


I have found the following quotes. Quote $1$ ( source ):




In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($omega_1^text{CK}$). In googology, BB oracles correspond to $ omega_1^text{CK} times 2 $ to the FGH.




(note that “BB oracles” here denote the oracles that can compute the Busy Beaver function for the lower-order Turing machines).



Quote $2$ ( source ):




With access to the halting oracle, you still cannot compute ordinals greater than $ omega_1^text{CK} $. The set of computable ordinals is, in fact, still the same. However, given an oracle for $ omega_1^text{CK} $, we can compute larger ordinals, and in fact the ordinals computable from $ omega_1^text{CK} $ are exactly the ones below $ omega_2^text{CK} $.




(in this quote, I don’t understand what “an oracle for $omega_1^text{CK}$” means).



Quote $3$ ( source ):




Adam Goucher admited he was wrong when he first wrote about strength of $Sigma_2(n)$. It is actually $omega_2^{CK}$, well over $omega_1^{CK} times 2$.




(note that $Sigma_2(n)$ here denotes the Busy Beaver function for the second-order oracle Turing machines, that is, Turing machines equipped with an oracle that can compute the Busy Beaver function for the first-order Turing machines).



It seems like Quote $3$ contradicts Quote $1$, and the question is: is it possible (if yes, then how?) to construct a model of Turing machines that correspond to $ omega_n^text{CK} $ in computability theory, assuming that $n$ can be extended to any natural number greater than $1$? What function would the oracles of such machines compute?



EDIT



Quote $4$ ( source ):




The first two admissible ordinals are ω and $omega _{1}^{mathrm {CK} }$ (the least non-recursive ordinal, also called the Church–Kleene ordinal). Any regular uncountable cardinal is an admissible ordinal.



By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.




Can anyone explain how exactly such construction is done? I cannot find any accessible explanation online.



There are relatively similar questions, but they do not address the described problem:





  • Is there a second Church-Kleene ordinal?

  • What classification of countable ordinals above $omega _{1}^{mathrm {CK} }$ exists?






logic ordinals turing-machines oracles







share|cite|improve this question











$endgroup$




I have found the following quotes. Quote $1$ ( source ):




In computability theory, Turing Machines+BB oracles correspond to the same ordinal as ordinary Turing Machines ($omega_1^text{CK}$). In googology, BB oracles correspond to $ omega_1^text{CK} times 2 $ to the FGH.




(note that “BB oracles” here denote the oracles that can compute the Busy Beaver function for the lower-order Turing machines).



Quote $2$ ( source ):




With access to the halting oracle, you still cannot compute ordinals greater than $ omega_1^text{CK} $. The set of computable ordinals is, in fact, still the same. However, given an oracle for $ omega_1^text{CK} $, we can compute larger ordinals, and in fact the ordinals computable from $ omega_1^text{CK} $ are exactly the ones below $ omega_2^text{CK} $.




(in this quote, I don’t understand what “an oracle for $omega_1^text{CK}$” means).



Quote $3$ ( source ):




Adam Goucher admited he was wrong when he first wrote about strength of $Sigma_2(n)$. It is actually $omega_2^{CK}$, well over $omega_1^{CK} times 2$.




(note that $Sigma_2(n)$ here denotes the Busy Beaver function for the second-order oracle Turing machines, that is, Turing machines equipped with an oracle that can compute the Busy Beaver function for the first-order Turing machines).



It seems like Quote $3$ contradicts Quote $1$, and the question is: is it possible (if yes, then how?) to construct a model of Turing machines that correspond to $ omega_n^text{CK} $ in computability theory, assuming that $n$ can be extended to any natural number greater than $1$? What function would the oracles of such machines compute?



EDIT



Quote $4$ ( source ):




The first two admissible ordinals are ω and $omega _{1}^{mathrm {CK} }$ (the least non-recursive ordinal, also called the Church–Kleene ordinal). Any regular uncountable cardinal is an admissible ordinal.



By a theorem of Sacks, the countable admissible ordinals are exactly those constructed in a manner similar to the Church-Kleene ordinal, but for Turing machines with oracles.




Can anyone explain how exactly such construction is done? I cannot find any accessible explanation online.



There are relatively similar questions, but they do not address the described problem:





  • Is there a second Church-Kleene ordinal?

  • What classification of countable ordinals above $omega _{1}^{mathrm {CK} }$ exists?






logic ordinals turing-machines oracles




logic ordinals turing-machines oracles






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Sep 6 '18 at 8:19







lyrically wicked

















asked Sep 4 '18 at 7:14









lyrically wickedlyrically wicked

20818




20818












  • $begingroup$
    Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:25










  • $begingroup$
    Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:27










  • $begingroup$
    Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:53










  • $begingroup$
    @Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
    $endgroup$
    – lyrically wicked
    Sep 4 '18 at 8:29










  • $begingroup$
    @Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
    $endgroup$
    – SSequence
    Sep 6 '18 at 9:23




















  • $begingroup$
    Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:25










  • $begingroup$
    Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:27










  • $begingroup$
    Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
    $endgroup$
    – Wojowu
    Sep 4 '18 at 7:53










  • $begingroup$
    @Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
    $endgroup$
    – lyrically wicked
    Sep 4 '18 at 8:29










  • $begingroup$
    @Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
    $endgroup$
    – SSequence
    Sep 6 '18 at 9:23


















$begingroup$
Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
$endgroup$
– Wojowu
Sep 4 '18 at 7:25




$begingroup$
Just so you know, all the "strength of function in terms of ordinals" claims are almost completely unsubstantiated - there is no formal way in which they are true. For the record, I am in large part a cause for the claim in quote 3, but since then I have learnt better and can assure you $Sigma_2$ in no sensible way reaches $omega_2^{CK}$.
$endgroup$
– Wojowu
Sep 4 '18 at 7:25












$begingroup$
Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
$endgroup$
– Wojowu
Sep 4 '18 at 7:27




$begingroup$
Regarding quote 2, "oracle for $omega_1^{CK}$" is any oracle which encodes a well-order of order type $omega_1^{CK}$. Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle we will no larger ordinals will be computable with this oracle.
$endgroup$
– Wojowu
Sep 4 '18 at 7:27












$begingroup$
Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
$endgroup$
– Wojowu
Sep 4 '18 at 7:53




$begingroup$
Again, we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean, but for the former, there is a reasonable answer of "doesn't reach $omega_2^{CK}$", because $omega$-th order halting oracle doesn't let us compute ordinals greater than $omega_1^{CK}$. For $BB_{omega_1^{CK}}$ we reach another issue of how exactly we would define $omega_1^{CK}$-th order oracle - there is no canonical way to do that (for recursive ordinals, we can show all (computable) choices give essentially the same oracle, but that fails for nonrecursive ordinals)
$endgroup$
– Wojowu
Sep 4 '18 at 7:53












$begingroup$
@Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
$endgroup$
– lyrically wicked
Sep 4 '18 at 8:29




$begingroup$
@Wojowu: —> we run into the problem of what "[a function] reaches [an ordinal]" is supposed to mean <— In this context, I think that this is the Busy Beaver function for Turing machines with an oracle which encodes a well-order of order type $omega_n^text{CK}$. But I still don't understand how to define these oracles. Even if there is no canonical way to do this, I think that any mathematically reasonable way would be enough.
$endgroup$
– lyrically wicked
Sep 4 '18 at 8:29












$begingroup$
@Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
$endgroup$
– SSequence
Sep 6 '18 at 9:23






$begingroup$
@Wojowu Can you give a specific reference (or references) for the result you mentioned in the second comment below the question? Also am I right in assuming that $omega_2^{CK}=omega_1^{CK}(omega_1^{CK})$ is considered as definition of $omega_2^{CK}$? Here I am assuming the following def. for $omega_1^{CK}(alpha)$ from an answer in linked thread (in question): "For $alpha$ an ordinal, we write $omega_1^{CK}(alpha)$ for the least ordinal $beta$ for which there is some copy of $alpha$ (= binary relation on $omega$ with ordertype $alpha$) which does not compute a copy of $beta$."
$endgroup$
– SSequence
Sep 6 '18 at 9:23












2 Answers
2






active

oldest

votes


















1












$begingroup$

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $omegacdot2$ example).






  • We begin with the computability side. For $r$ a real, we let $omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $mathcal{A}$ we let $omega_1^{CK}(mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $mathcal{A}$; precisely, $$omega_1^{CK}(mathcal{A})=min{omega_1^{CK}(r):rmbox{ codes a copy of $mathcal{A}$}}.$$




    • "$omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $rsubseteqomega$ with the structure $hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $omega_1^{CK}(r)=omega_1^{CK}(hat{r})$, so everything lines up nicely.




  • Next, we look at the admissibility side. For $alpha$ an arbitrary ordinal, we let $omega_alpha^{ad}$ denote the $alpha$th admissible ordinal: that is, the $alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $alpha$ to be countable!). We'll also write "$omega_1^{ad}(beta)$" for the first admissible ordinal $>beta$; in particular, $omega_1^{ad}(omega_alpha^{ad})=omega_{alpha+1}^{ad}$.





    • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.




  • Now Sacks' result (plus a bit of thought) shows that $$omega_1^{CK}(alpha)=omega_1^{ad}(alpha)mbox{ for every countable ordinal $alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$omega_alpha^{CK}$" is just our "$omega_alpha^{ad}$."




    • Moreover, Sacks' result immediately implies that $omega_1^{CK}(mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.


    • Also, via forcing we can make sense of this for even uncountable $alpha$. But that's really a side issue.






$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $omega_1^{CK}(mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.



Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $nin 0'$ gives a copy of $omega$ which computes $0'$, and more generally we can get copies of $omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.




  • Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$.


What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $mathcal{A}le_wmathcal{B}$ if every real coding a copy of $mathcal{B}$ computes some real coding a copy of $mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.



EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $le$ - if $mathcal{A}ge_walpha$ and $beta<alpha$ then $mathcal{A}ge_wbeta$. In particular this means that $omega_1^{CK}(mathcal{A})$ is both the least ordinal without a copy computable from every copy of $mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $mathcal{A}$.



EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $omega_1^{CK}$: a copy of $omega_1^{CK}$ can be computed straightforwardly from Kleene's $mathcal{O}$, but$^2$ $mathcal{O}$ is in $L_{omega_2^{CK}}$ and so every ordinal with a copy computable from $mathcal{O}$ is $<omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    > the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
    $endgroup$
    – lyrically wicked
    Feb 3 at 2:54












  • $begingroup$
    @lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
    $endgroup$
    – Noah Schweber
    Feb 3 at 3:16










  • $begingroup$
    You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
    $endgroup$
    – lyrically wicked
    Feb 3 at 3:38








  • 1




    $begingroup$
    (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
    $endgroup$
    – Noah Schweber
    Feb 3 at 4:32






  • 1




    $begingroup$
    @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
    $endgroup$
    – Noah Schweber
    Feb 3 at 14:59



















0












$begingroup$

This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A subseteq mathbb{N}$ be any set such that $Ain HA$ (HA=hyperarithmethic). Then you can't generate $omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H in HYP$, one gets the result mentioned in the first half of [Quote2].



I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).



Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$.



For example, if you defined a function $LE:mathbb{N}^2 rightarrow mathbb{N}$ so that:



$LE(x,y)=1$ if and only if $x le y$



then $LE$ represent the well-order relation ..... corresponding to well-ordering of $mathbb{N}$ with order-type $omega$.



Another example is:



$LE(x,y)=1$ if $x=y$



If $x ne y$ then:



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even



$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd



$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd



If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $mathbb{N}$ with order-type $omega cdot 2$.



Similarly you can also describe a well-ordering of $mathbb{N}$ with order-type $omega^2$ using a pairing function (a function describing a 1-1 correspondence between $mathbb{N}^2$ and $mathbb{N}$).




Now coming back to the comment in second half of [Quote2]. If you denote $alpha=omega_{CK}=omega^{CK}_1$ and denote, for example, $beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):



$beta > alpha cdot 2$



$beta > alpha ^ 2$



$beta > alpha ^ alpha$



$beta > gamma=sup{alpha, alpha^alpha, alpha^{alpha^alpha},..... }$



this goes on...






share|cite|improve this answer











$endgroup$













  • $begingroup$
    But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
    $endgroup$
    – SSequence
    Sep 5 '18 at 9:43












  • $begingroup$
    Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
    $endgroup$
    – SSequence
    Sep 8 '18 at 16:11












Your Answer








StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2904721%2fis-it-possible-to-construct-a-model-of-oracle-turing-machines-that-correspond-to%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $omegacdot2$ example).






  • We begin with the computability side. For $r$ a real, we let $omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $mathcal{A}$ we let $omega_1^{CK}(mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $mathcal{A}$; precisely, $$omega_1^{CK}(mathcal{A})=min{omega_1^{CK}(r):rmbox{ codes a copy of $mathcal{A}$}}.$$




    • "$omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $rsubseteqomega$ with the structure $hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $omega_1^{CK}(r)=omega_1^{CK}(hat{r})$, so everything lines up nicely.




  • Next, we look at the admissibility side. For $alpha$ an arbitrary ordinal, we let $omega_alpha^{ad}$ denote the $alpha$th admissible ordinal: that is, the $alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $alpha$ to be countable!). We'll also write "$omega_1^{ad}(beta)$" for the first admissible ordinal $>beta$; in particular, $omega_1^{ad}(omega_alpha^{ad})=omega_{alpha+1}^{ad}$.





    • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.




  • Now Sacks' result (plus a bit of thought) shows that $$omega_1^{CK}(alpha)=omega_1^{ad}(alpha)mbox{ for every countable ordinal $alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$omega_alpha^{CK}$" is just our "$omega_alpha^{ad}$."




    • Moreover, Sacks' result immediately implies that $omega_1^{CK}(mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.


    • Also, via forcing we can make sense of this for even uncountable $alpha$. But that's really a side issue.






$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $omega_1^{CK}(mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.



Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $nin 0'$ gives a copy of $omega$ which computes $0'$, and more generally we can get copies of $omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.




  • Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$.


What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $mathcal{A}le_wmathcal{B}$ if every real coding a copy of $mathcal{B}$ computes some real coding a copy of $mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.



EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $le$ - if $mathcal{A}ge_walpha$ and $beta<alpha$ then $mathcal{A}ge_wbeta$. In particular this means that $omega_1^{CK}(mathcal{A})$ is both the least ordinal without a copy computable from every copy of $mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $mathcal{A}$.



EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $omega_1^{CK}$: a copy of $omega_1^{CK}$ can be computed straightforwardly from Kleene's $mathcal{O}$, but$^2$ $mathcal{O}$ is in $L_{omega_2^{CK}}$ and so every ordinal with a copy computable from $mathcal{O}$ is $<omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    > the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
    $endgroup$
    – lyrically wicked
    Feb 3 at 2:54












  • $begingroup$
    @lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
    $endgroup$
    – Noah Schweber
    Feb 3 at 3:16










  • $begingroup$
    You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
    $endgroup$
    – lyrically wicked
    Feb 3 at 3:38








  • 1




    $begingroup$
    (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
    $endgroup$
    – Noah Schweber
    Feb 3 at 4:32






  • 1




    $begingroup$
    @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
    $endgroup$
    – Noah Schweber
    Feb 3 at 14:59
















1












$begingroup$

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $omegacdot2$ example).






  • We begin with the computability side. For $r$ a real, we let $omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $mathcal{A}$ we let $omega_1^{CK}(mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $mathcal{A}$; precisely, $$omega_1^{CK}(mathcal{A})=min{omega_1^{CK}(r):rmbox{ codes a copy of $mathcal{A}$}}.$$




    • "$omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $rsubseteqomega$ with the structure $hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $omega_1^{CK}(r)=omega_1^{CK}(hat{r})$, so everything lines up nicely.




  • Next, we look at the admissibility side. For $alpha$ an arbitrary ordinal, we let $omega_alpha^{ad}$ denote the $alpha$th admissible ordinal: that is, the $alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $alpha$ to be countable!). We'll also write "$omega_1^{ad}(beta)$" for the first admissible ordinal $>beta$; in particular, $omega_1^{ad}(omega_alpha^{ad})=omega_{alpha+1}^{ad}$.





    • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.




  • Now Sacks' result (plus a bit of thought) shows that $$omega_1^{CK}(alpha)=omega_1^{ad}(alpha)mbox{ for every countable ordinal $alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$omega_alpha^{CK}$" is just our "$omega_alpha^{ad}$."




    • Moreover, Sacks' result immediately implies that $omega_1^{CK}(mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.


    • Also, via forcing we can make sense of this for even uncountable $alpha$. But that's really a side issue.






$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $omega_1^{CK}(mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.



Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $nin 0'$ gives a copy of $omega$ which computes $0'$, and more generally we can get copies of $omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.




  • Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$.


What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $mathcal{A}le_wmathcal{B}$ if every real coding a copy of $mathcal{B}$ computes some real coding a copy of $mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.



EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $le$ - if $mathcal{A}ge_walpha$ and $beta<alpha$ then $mathcal{A}ge_wbeta$. In particular this means that $omega_1^{CK}(mathcal{A})$ is both the least ordinal without a copy computable from every copy of $mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $mathcal{A}$.



EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $omega_1^{CK}$: a copy of $omega_1^{CK}$ can be computed straightforwardly from Kleene's $mathcal{O}$, but$^2$ $mathcal{O}$ is in $L_{omega_2^{CK}}$ and so every ordinal with a copy computable from $mathcal{O}$ is $<omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    > the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
    $endgroup$
    – lyrically wicked
    Feb 3 at 2:54












  • $begingroup$
    @lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
    $endgroup$
    – Noah Schweber
    Feb 3 at 3:16










  • $begingroup$
    You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
    $endgroup$
    – lyrically wicked
    Feb 3 at 3:38








  • 1




    $begingroup$
    (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
    $endgroup$
    – Noah Schweber
    Feb 3 at 4:32






  • 1




    $begingroup$
    @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
    $endgroup$
    – Noah Schweber
    Feb 3 at 14:59














1












1








1





$begingroup$

Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $omegacdot2$ example).






  • We begin with the computability side. For $r$ a real, we let $omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $mathcal{A}$ we let $omega_1^{CK}(mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $mathcal{A}$; precisely, $$omega_1^{CK}(mathcal{A})=min{omega_1^{CK}(r):rmbox{ codes a copy of $mathcal{A}$}}.$$




    • "$omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $rsubseteqomega$ with the structure $hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $omega_1^{CK}(r)=omega_1^{CK}(hat{r})$, so everything lines up nicely.




  • Next, we look at the admissibility side. For $alpha$ an arbitrary ordinal, we let $omega_alpha^{ad}$ denote the $alpha$th admissible ordinal: that is, the $alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $alpha$ to be countable!). We'll also write "$omega_1^{ad}(beta)$" for the first admissible ordinal $>beta$; in particular, $omega_1^{ad}(omega_alpha^{ad})=omega_{alpha+1}^{ad}$.





    • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.




  • Now Sacks' result (plus a bit of thought) shows that $$omega_1^{CK}(alpha)=omega_1^{ad}(alpha)mbox{ for every countable ordinal $alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$omega_alpha^{CK}$" is just our "$omega_alpha^{ad}$."




    • Moreover, Sacks' result immediately implies that $omega_1^{CK}(mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.


    • Also, via forcing we can make sense of this for even uncountable $alpha$. But that's really a side issue.






$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $omega_1^{CK}(mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.



Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $nin 0'$ gives a copy of $omega$ which computes $0'$, and more generally we can get copies of $omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.




  • Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$.


What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $mathcal{A}le_wmathcal{B}$ if every real coding a copy of $mathcal{B}$ computes some real coding a copy of $mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.



EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $le$ - if $mathcal{A}ge_walpha$ and $beta<alpha$ then $mathcal{A}ge_wbeta$. In particular this means that $omega_1^{CK}(mathcal{A})$ is both the least ordinal without a copy computable from every copy of $mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $mathcal{A}$.



EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $omega_1^{CK}$: a copy of $omega_1^{CK}$ can be computed straightforwardly from Kleene's $mathcal{O}$, but$^2$ $mathcal{O}$ is in $L_{omega_2^{CK}}$ and so every ordinal with a copy computable from $mathcal{O}$ is $<omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.






share|cite|improve this answer











$endgroup$



Throughout, by "structure" I mean "countable structure in a computable language." I'm also assuming you're comfortable both with Turing reducibility $le_T$ - which lets us avoid unnecessary verbiage about machines and oracles - and with the idea of reals coding copies of structures (see SSequence's answer, specifically the $omegacdot2$ example).






  • We begin with the computability side. For $r$ a real, we let $omega_1^{CK}(r)$ be the smallest ordinal with no $r$-computable copy; equivalently, the supremum of the ordinals which do have $r$-computable copies. For a structure $mathcal{A}$ we let $omega_1^{CK}(mathcal{A})$ be the smallest ordinal not computed by some$^1$ copy of $mathcal{A}$; precisely, $$omega_1^{CK}(mathcal{A})=min{omega_1^{CK}(r):rmbox{ codes a copy of $mathcal{A}$}}.$$




    • "$omega_1^{CK}(r)$" is not how that appears in the literature - rather, you'll see "$omega_1^r$" - but I strongly prefer it, since it avoids clashing with set-theoretic notation. Note also that we can conflate a real $rsubseteqomega$ with the structure $hat{r}$ consisting of the natural numbers with successor and a unary predicate for $r$, and it's easy to check that $omega_1^{CK}(r)=omega_1^{CK}(hat{r})$, so everything lines up nicely.




  • Next, we look at the admissibility side. For $alpha$ an arbitrary ordinal, we let $omega_alpha^{ad}$ denote the $alpha$th admissible ordinal: that is, the $alpha$th ordinal whose corresponding level of $L$ satisfies KP. Note that this definition has nothing to do with computability theory on the face of it (and in fact, doesn't even require $alpha$ to be countable!). We'll also write "$omega_1^{ad}(beta)$" for the first admissible ordinal $>beta$; in particular, $omega_1^{ad}(omega_alpha^{ad})=omega_{alpha+1}^{ad}$.





    • Nobody uses this notation, since by Sacks' result it's completely redundant. However, distinguishing at this stage in the game between admissibility concerns and computability concerns is I think very helpful, so I hope you'll forgive me the introduction of soon-to-be-stupid notation.




  • Now Sacks' result (plus a bit of thought) shows that $$omega_1^{CK}(alpha)=omega_1^{ad}(alpha)mbox{ for every countable ordinal $alpha$}.$$ This is why you never see the "$ad$" notation: it's made completely irrelevant! In particular, "$omega_alpha^{CK}$" is just our "$omega_alpha^{ad}$."




    • Moreover, Sacks' result immediately implies that $omega_1^{CK}(mathcal{A})$, being the minimum of a set of admissible ordinals,is itself admissible.


    • Also, via forcing we can make sense of this for even uncountable $alpha$. But that's really a side issue.






$^1$Note the careful quantification over copies here (and the implicit focus on "optimally simple" copies) in our definition of $omega_1^{CK}(mathcal{A})$. This is fundamental: different copies of the same structure can behave very differently, and we need to address this if our definitions are to be interesting at all.



Specifically, we can have very simple structures coded by very complicated reals: e.g. "swapping" $2n$ and $2n+1$ whenever $nin 0'$ gives a copy of $omega$ which computes $0'$, and more generally we can get copies of $omega$ of arbitrarily high complexity. In fact, this (almost) always happens. So in order to say anything interesting, we need to talk about what all copies of a given structure can do.




  • Note: this is what Wojowu's comment "Results due to Sacks imply that with such an oracle we can compute all ordinals below $omega_2^{CK}$, and for suitable choice of this oracle [typo removed] no larger ordinals will be computable with this oracle." Obviously some copies of $omega_2^{CK}$, when used as oracles, will let us compute a ton of extra junk; the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$.


What we're ultimately getting at here is the idea of reducibilities between structures. Here we're looking just at Muchnik (weak) reducibility: $mathcal{A}le_wmathcal{B}$ if every real coding a copy of $mathcal{B}$ computes some real coding a copy of $mathcal{A}$. There are other reducibilities too - most immediately, Medvedev (strong) reducibility - but for these sorts of questions we're really in the Muchnik realm, at least for now.



EDIT: An important point here which I think will substantially clarify things is that Muchnik reducibility extends $le$ - if $mathcal{A}ge_walpha$ and $beta<alpha$ then $mathcal{A}ge_wbeta$. In particular this means that $omega_1^{CK}(mathcal{A})$ is both the least ordinal without a copy computable from every copy of $mathcal{A}$, and the supremum of the ordinals which do have copies computable from every copy of $mathcal{A}$.



EDIT THE SECOND: And here's a way of constructing such a "sufficiently simple" copy of $omega_1^{CK}$: a copy of $omega_1^{CK}$ can be computed straightforwardly from Kleene's $mathcal{O}$, but$^2$ $mathcal{O}$ is in $L_{omega_2^{CK}}$ and so every ordinal with a copy computable from $mathcal{O}$ is $<omega_2^{CK}$. All of this requires a bit of familiarity with admissible sets and $L_{omega_1^{CK}}$ in particular; Sacks' book is as usual a good source on the topic.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Feb 3 at 14:59

























answered Feb 2 at 19:59









Noah SchweberNoah Schweber

129k10152294




129k10152294












  • $begingroup$
    > the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
    $endgroup$
    – lyrically wicked
    Feb 3 at 2:54












  • $begingroup$
    @lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
    $endgroup$
    – Noah Schweber
    Feb 3 at 3:16










  • $begingroup$
    You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
    $endgroup$
    – lyrically wicked
    Feb 3 at 3:38








  • 1




    $begingroup$
    (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
    $endgroup$
    – Noah Schweber
    Feb 3 at 4:32






  • 1




    $begingroup$
    @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
    $endgroup$
    – Noah Schweber
    Feb 3 at 14:59


















  • $begingroup$
    > the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
    $endgroup$
    – lyrically wicked
    Feb 3 at 2:54












  • $begingroup$
    @lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
    $endgroup$
    – Noah Schweber
    Feb 3 at 3:16










  • $begingroup$
    You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
    $endgroup$
    – lyrically wicked
    Feb 3 at 3:38








  • 1




    $begingroup$
    (This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
    $endgroup$
    – Noah Schweber
    Feb 3 at 4:32






  • 1




    $begingroup$
    @lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
    $endgroup$
    – Noah Schweber
    Feb 3 at 14:59
















$begingroup$
> the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
$endgroup$
– lyrically wicked
Feb 3 at 2:54






$begingroup$
> the point is that nothing beyond $omega_2^{CK}$ is necessarily computable from a copy of $omega_1^{CK}$ < I am not sure I understand the word "beyond" here correctly. Does it mean "below" or "above"?
$endgroup$
– lyrically wicked
Feb 3 at 2:54














$begingroup$
@lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
$endgroup$
– Noah Schweber
Feb 3 at 3:16




$begingroup$
@lyricallywicked above. If $r$ is a real coding a copy of $omega_1^{CK}$, then every ordinal less than $omega_1^{CK}$ has a copy computable from $r$ (and no ordinal $geomega_2^{CK}$ is guaranteed to have a copy computable from $r$).
$endgroup$
– Noah Schweber
Feb 3 at 3:16












$begingroup$
You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
$endgroup$
– lyrically wicked
Feb 3 at 3:38






$begingroup$
You mentioned "every ordinal less than $omega_1^{CK}$" and "ordinal $ge omega_2^{CK}$". But where are all ordinals less than $omega_2^{CK}$? Are their copies guaranteed to be computable?
$endgroup$
– lyrically wicked
Feb 3 at 3:38






1




1




$begingroup$
(This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
$endgroup$
– Noah Schweber
Feb 3 at 4:32




$begingroup$
(This then makes phrases like "real coding a copy of" redundant.) In this language, what I said above would be just: "If $r$ is a copy of $omega_1^{CK}$, then every ordinal $<omega_2^{CK}$ has an $r$-computable copy; on the other hand, there is a copy $s$ of $omega_1^{CK}$ which doesn't compute copies of any ordinal $geomega_2^{CK}$."
$endgroup$
– Noah Schweber
Feb 3 at 4:32




1




1




$begingroup$
@lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
$endgroup$
– Noah Schweber
Feb 3 at 14:59




$begingroup$
@lyricallywicked I've added a bit about producing a "sufficiently simple" copy of $omega_1^{CK}$.
$endgroup$
– Noah Schweber
Feb 3 at 14:59











0












$begingroup$

This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A subseteq mathbb{N}$ be any set such that $Ain HA$ (HA=hyperarithmethic). Then you can't generate $omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H in HYP$, one gets the result mentioned in the first half of [Quote2].



I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).



Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$.



For example, if you defined a function $LE:mathbb{N}^2 rightarrow mathbb{N}$ so that:



$LE(x,y)=1$ if and only if $x le y$



then $LE$ represent the well-order relation ..... corresponding to well-ordering of $mathbb{N}$ with order-type $omega$.



Another example is:



$LE(x,y)=1$ if $x=y$



If $x ne y$ then:



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even



$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd



$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd



If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $mathbb{N}$ with order-type $omega cdot 2$.



Similarly you can also describe a well-ordering of $mathbb{N}$ with order-type $omega^2$ using a pairing function (a function describing a 1-1 correspondence between $mathbb{N}^2$ and $mathbb{N}$).




Now coming back to the comment in second half of [Quote2]. If you denote $alpha=omega_{CK}=omega^{CK}_1$ and denote, for example, $beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):



$beta > alpha cdot 2$



$beta > alpha ^ 2$



$beta > alpha ^ alpha$



$beta > gamma=sup{alpha, alpha^alpha, alpha^{alpha^alpha},..... }$



this goes on...






share|cite|improve this answer











$endgroup$













  • $begingroup$
    But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
    $endgroup$
    – SSequence
    Sep 5 '18 at 9:43












  • $begingroup$
    Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
    $endgroup$
    – SSequence
    Sep 8 '18 at 16:11
















0












$begingroup$

This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A subseteq mathbb{N}$ be any set such that $Ain HA$ (HA=hyperarithmethic). Then you can't generate $omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H in HYP$, one gets the result mentioned in the first half of [Quote2].



I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).



Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$.



For example, if you defined a function $LE:mathbb{N}^2 rightarrow mathbb{N}$ so that:



$LE(x,y)=1$ if and only if $x le y$



then $LE$ represent the well-order relation ..... corresponding to well-ordering of $mathbb{N}$ with order-type $omega$.



Another example is:



$LE(x,y)=1$ if $x=y$



If $x ne y$ then:



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even



$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd



$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd



If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $mathbb{N}$ with order-type $omega cdot 2$.



Similarly you can also describe a well-ordering of $mathbb{N}$ with order-type $omega^2$ using a pairing function (a function describing a 1-1 correspondence between $mathbb{N}^2$ and $mathbb{N}$).




Now coming back to the comment in second half of [Quote2]. If you denote $alpha=omega_{CK}=omega^{CK}_1$ and denote, for example, $beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):



$beta > alpha cdot 2$



$beta > alpha ^ 2$



$beta > alpha ^ alpha$



$beta > gamma=sup{alpha, alpha^alpha, alpha^{alpha^alpha},..... }$



this goes on...






share|cite|improve this answer











$endgroup$













  • $begingroup$
    But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
    $endgroup$
    – SSequence
    Sep 5 '18 at 9:43












  • $begingroup$
    Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
    $endgroup$
    – SSequence
    Sep 8 '18 at 16:11














0












0








0





$begingroup$

This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A subseteq mathbb{N}$ be any set such that $Ain HA$ (HA=hyperarithmethic). Then you can't generate $omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H in HYP$, one gets the result mentioned in the first half of [Quote2].



I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).



Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$.



For example, if you defined a function $LE:mathbb{N}^2 rightarrow mathbb{N}$ so that:



$LE(x,y)=1$ if and only if $x le y$



then $LE$ represent the well-order relation ..... corresponding to well-ordering of $mathbb{N}$ with order-type $omega$.



Another example is:



$LE(x,y)=1$ if $x=y$



If $x ne y$ then:



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even



$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd



$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd



If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $mathbb{N}$ with order-type $omega cdot 2$.



Similarly you can also describe a well-ordering of $mathbb{N}$ with order-type $omega^2$ using a pairing function (a function describing a 1-1 correspondence between $mathbb{N}^2$ and $mathbb{N}$).




Now coming back to the comment in second half of [Quote2]. If you denote $alpha=omega_{CK}=omega^{CK}_1$ and denote, for example, $beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):



$beta > alpha cdot 2$



$beta > alpha ^ 2$



$beta > alpha ^ alpha$



$beta > gamma=sup{alpha, alpha^alpha, alpha^{alpha^alpha},..... }$



this goes on...






share|cite|improve this answer











$endgroup$



This really should be a comment, but probably too long for it. Regarding [Quote2], I think it follows from a general and rather well-known result. Let $A subseteq mathbb{N}$ be any set such that $Ain HA$ (HA=hyperarithmethic). Then you can't generate $omega_{CK}$ with a program that has access to the set $A$. If you denote $H$ as halt-set then because $H in HYP$, one gets the result mentioned in the first half of [Quote2].



I do not have any familiarity with the result personally though (it was mentioned in the first question I asked an year ago).



Also regarding the second half of [Quote2], since you mentioned you don't understand what an "oracle for $omega_{CK}$ means", here are few comments that might help. I am not good with formal stuff so I hope there isn't an issue in the wording. But formally I think it means having an access to function(or an equivalent set basically) which represents the well-order relation ...... corresponding to the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$.



For example, if you defined a function $LE:mathbb{N}^2 rightarrow mathbb{N}$ so that:



$LE(x,y)=1$ if and only if $x le y$



then $LE$ represent the well-order relation ..... corresponding to well-ordering of $mathbb{N}$ with order-type $omega$.



Another example is:



$LE(x,y)=1$ if $x=y$



If $x ne y$ then:



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is even and $y$ is even



$LE(x,y)=1$ ---- if $x$ is even and $y$ is odd



$LE(x,y)=0$ ---- if $x$ is odd and $y$ is even



$LE(x,y)=$ truth value of $x<y$ ---- if $x$ is odd and $y$ is odd



If you look at it carefully enough, $LE$ here represents the well-order relation corresponding to well-ordering of $mathbb{N}$ with order-type $omega cdot 2$.



Similarly you can also describe a well-ordering of $mathbb{N}$ with order-type $omega^2$ using a pairing function (a function describing a 1-1 correspondence between $mathbb{N}^2$ and $mathbb{N}$).




Now coming back to the comment in second half of [Quote2]. If you denote $alpha=omega_{CK}=omega^{CK}_1$ and denote, for example, $beta$ as the smallest ordinal that can't be generated using a program that has access to the well-order relation describing the well-ordering of $omega_{CK}$ in terms of $mathbb{N}$. Then I hope you can easily see why the following should all be true (via a positive demonstration of a program that does it):



$beta > alpha cdot 2$



$beta > alpha ^ 2$



$beta > alpha ^ alpha$



$beta > gamma=sup{alpha, alpha^alpha, alpha^{alpha^alpha},..... }$



this goes on...







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Sep 8 '18 at 16:11

























answered Sep 5 '18 at 9:15









SSequenceSSequence

55729




55729












  • $begingroup$
    But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
    $endgroup$
    – SSequence
    Sep 5 '18 at 9:43












  • $begingroup$
    Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
    $endgroup$
    – SSequence
    Sep 8 '18 at 16:11


















  • $begingroup$
    But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
    $endgroup$
    – SSequence
    Sep 5 '18 at 9:43












  • $begingroup$
    Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
    $endgroup$
    – SSequence
    Sep 8 '18 at 16:11
















$begingroup$
But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
$endgroup$
– SSequence
Sep 5 '18 at 9:43






$begingroup$
But there is one more subtlety to it in the sense that the choice of well-order relation for $omega_{CK}$ could change $beta$. See the second comment by @Wojowu below the question. I am guessing that possibly the phrase "and for suitable choice of this oracle" is meant to reflect this.
$endgroup$
– SSequence
Sep 5 '18 at 9:43














$begingroup$
Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
$endgroup$
– SSequence
Sep 8 '18 at 16:11




$begingroup$
Bumped to correct somewhat misleading phrase "well-ordering of $omega^2$ (in terms of $mathbb{N}$)"
$endgroup$
– SSequence
Sep 8 '18 at 16:11


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2904721%2fis-it-possible-to-construct-a-model-of-oracle-turing-machines-that-correspond-to%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

MongoDB - Not Authorized To Execute Command

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
Read more

How to fix TextFormField cause rebuild widget in Flutter

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
Read more

Npm cannot find a required file even through it is in the searched directory

Image
up vote 0 down vote favorite I got that error: users-Air:pdfuploader user$ npm run start client@0.1.0 start /Users/user/Documents/pdfuploader react-scripts start Could not find a required file. Name: index.html Searched in: /Users/user/Documents/pdfuploader/public npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! client@0.1.0 start: `react-scripts start` npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the client@0.1.0 start script. npm ERR! This is probably not a problem with npm. There is likely additional logging output above. npm ERR! A complete log of this run can be found in: npm ERR! /Users/user/.npm/_logs/2018-11-19T10_19_14_555Z-debug.log users-Air:pdfuploader user$ And the file is in /Users/user/Documents/pdfuploader/public as you can see in my github repository: https://github.c...
Read more