What is the source of formal descriptions for large uncomputable ordinals clockable by Infinite Time Turing...












1












$begingroup$


I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $alpha$ if $alpha$ is a computable ordinal: basically, we take the description of some standard Turing machine $M_i$ and use the wellorder that it encodes. Then we analyze the computational process of an ITTM using the ordinal that corresponds to $M_i$.



But if we want to analyze the computational process when $alpha$ is uncomputable (assuming that Infinite Time Turing Machines can clock very large uncomputable ordinals), we need to obtain a precise description of $alpha$ somewhere. But where can we find formal descriptions of such ordinals in the first place (assuming that the set of these descriptions is required to be countable)?



EDIT

This question can be formulated as follows.



Imagine the existence of an oracle that always tells the truth. Assuming that you and the oracle solve problems of




given a natural number $x$, find an ITTM that is indexed by $x$




and




given a real number $x$, decode it as an ordinal




in exactly the same way, this oracle sends the following message:




I have chosen a natural number $N$. All I can tell you is that an ITTM indexed by $N$ clocks some ordinal $alpha$. You can send me any real number that encodes any ordinal, and I will immediately tell you whether this ordinal is equal to $alpha$ or not. You have an infinite amount of infinitely powerful computational resources and infinite amount of time. Moreover, if you send me any countable set $S$ of ordinals, I will send you a number $0$ if this set does not contain $alpha$; otherwise, I will send you a positive number $i$ such that an $i$-th element of $S$ is equal to $alpha$. And here are three rules that must be taken into account: (i) any set $S$ that you send me is required to be a set of real numbers, where each element encodes an ordinal in a particular (fixed) way. It is your choice to fix such encoding, but you must tell me about your choice so that we can interpret all reals in the same way; (ii) If you send me a countable set (described in the previous rule), then (assuming that we agree on a fixed algorithm that decodes a single real number into a countable set of real numbers) you are required to provide an exact description of an algorithm (namely, an index of an ITTM together with a real number that encodes an ordinal for a stage when the output tape is expected to contain the real number that encodes the entire set $S$) that generates $S$; (iii) for any ITTM indexed by any natural number $n$, you are allowed to ask for a real number that appears on the output tape at stage $beta$, but if and only if you provide a real number that encodes an ordinal $beta$ (in the same fixed way that you have chosen). You can store these numbers in arbitrary (finite/infinite) sets/multisets and operate with them in any way you want.

So, if you find $alpha$, you win.




Question: does there exist a way to always win, no matter which $N$ the oracle chooses? If yes, then how?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
    $endgroup$
    – Noah Schweber
    Dec 29 '18 at 18:20












  • $begingroup$
    @NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 8:49












  • $begingroup$
    @lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:12












  • $begingroup$
    Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:42










  • $begingroup$
    @NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:52
















1












$begingroup$


I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $alpha$ if $alpha$ is a computable ordinal: basically, we take the description of some standard Turing machine $M_i$ and use the wellorder that it encodes. Then we analyze the computational process of an ITTM using the ordinal that corresponds to $M_i$.



But if we want to analyze the computational process when $alpha$ is uncomputable (assuming that Infinite Time Turing Machines can clock very large uncomputable ordinals), we need to obtain a precise description of $alpha$ somewhere. But where can we find formal descriptions of such ordinals in the first place (assuming that the set of these descriptions is required to be countable)?



EDIT

This question can be formulated as follows.



Imagine the existence of an oracle that always tells the truth. Assuming that you and the oracle solve problems of




given a natural number $x$, find an ITTM that is indexed by $x$




and




given a real number $x$, decode it as an ordinal




in exactly the same way, this oracle sends the following message:




I have chosen a natural number $N$. All I can tell you is that an ITTM indexed by $N$ clocks some ordinal $alpha$. You can send me any real number that encodes any ordinal, and I will immediately tell you whether this ordinal is equal to $alpha$ or not. You have an infinite amount of infinitely powerful computational resources and infinite amount of time. Moreover, if you send me any countable set $S$ of ordinals, I will send you a number $0$ if this set does not contain $alpha$; otherwise, I will send you a positive number $i$ such that an $i$-th element of $S$ is equal to $alpha$. And here are three rules that must be taken into account: (i) any set $S$ that you send me is required to be a set of real numbers, where each element encodes an ordinal in a particular (fixed) way. It is your choice to fix such encoding, but you must tell me about your choice so that we can interpret all reals in the same way; (ii) If you send me a countable set (described in the previous rule), then (assuming that we agree on a fixed algorithm that decodes a single real number into a countable set of real numbers) you are required to provide an exact description of an algorithm (namely, an index of an ITTM together with a real number that encodes an ordinal for a stage when the output tape is expected to contain the real number that encodes the entire set $S$) that generates $S$; (iii) for any ITTM indexed by any natural number $n$, you are allowed to ask for a real number that appears on the output tape at stage $beta$, but if and only if you provide a real number that encodes an ordinal $beta$ (in the same fixed way that you have chosen). You can store these numbers in arbitrary (finite/infinite) sets/multisets and operate with them in any way you want.

So, if you find $alpha$, you win.




Question: does there exist a way to always win, no matter which $N$ the oracle chooses? If yes, then how?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
    $endgroup$
    – Noah Schweber
    Dec 29 '18 at 18:20












  • $begingroup$
    @NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 8:49












  • $begingroup$
    @lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:12












  • $begingroup$
    Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:42










  • $begingroup$
    @NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:52














1












1








1





$begingroup$


I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $alpha$ if $alpha$ is a computable ordinal: basically, we take the description of some standard Turing machine $M_i$ and use the wellorder that it encodes. Then we analyze the computational process of an ITTM using the ordinal that corresponds to $M_i$.



But if we want to analyze the computational process when $alpha$ is uncomputable (assuming that Infinite Time Turing Machines can clock very large uncomputable ordinals), we need to obtain a precise description of $alpha$ somewhere. But where can we find formal descriptions of such ordinals in the first place (assuming that the set of these descriptions is required to be countable)?



EDIT

This question can be formulated as follows.



Imagine the existence of an oracle that always tells the truth. Assuming that you and the oracle solve problems of




given a natural number $x$, find an ITTM that is indexed by $x$




and




given a real number $x$, decode it as an ordinal




in exactly the same way, this oracle sends the following message:




I have chosen a natural number $N$. All I can tell you is that an ITTM indexed by $N$ clocks some ordinal $alpha$. You can send me any real number that encodes any ordinal, and I will immediately tell you whether this ordinal is equal to $alpha$ or not. You have an infinite amount of infinitely powerful computational resources and infinite amount of time. Moreover, if you send me any countable set $S$ of ordinals, I will send you a number $0$ if this set does not contain $alpha$; otherwise, I will send you a positive number $i$ such that an $i$-th element of $S$ is equal to $alpha$. And here are three rules that must be taken into account: (i) any set $S$ that you send me is required to be a set of real numbers, where each element encodes an ordinal in a particular (fixed) way. It is your choice to fix such encoding, but you must tell me about your choice so that we can interpret all reals in the same way; (ii) If you send me a countable set (described in the previous rule), then (assuming that we agree on a fixed algorithm that decodes a single real number into a countable set of real numbers) you are required to provide an exact description of an algorithm (namely, an index of an ITTM together with a real number that encodes an ordinal for a stage when the output tape is expected to contain the real number that encodes the entire set $S$) that generates $S$; (iii) for any ITTM indexed by any natural number $n$, you are allowed to ask for a real number that appears on the output tape at stage $beta$, but if and only if you provide a real number that encodes an ordinal $beta$ (in the same fixed way that you have chosen). You can store these numbers in arbitrary (finite/infinite) sets/multisets and operate with them in any way you want.

So, if you find $alpha$, you win.




Question: does there exist a way to always win, no matter which $N$ the oracle chooses? If yes, then how?










share|cite|improve this question











$endgroup$




I can imagine the process of analyzing the computation of an ITTM at any limit stage denoted by $alpha$ if $alpha$ is a computable ordinal: basically, we take the description of some standard Turing machine $M_i$ and use the wellorder that it encodes. Then we analyze the computational process of an ITTM using the ordinal that corresponds to $M_i$.



But if we want to analyze the computational process when $alpha$ is uncomputable (assuming that Infinite Time Turing Machines can clock very large uncomputable ordinals), we need to obtain a precise description of $alpha$ somewhere. But where can we find formal descriptions of such ordinals in the first place (assuming that the set of these descriptions is required to be countable)?



EDIT

This question can be formulated as follows.



Imagine the existence of an oracle that always tells the truth. Assuming that you and the oracle solve problems of




given a natural number $x$, find an ITTM that is indexed by $x$




and




given a real number $x$, decode it as an ordinal




in exactly the same way, this oracle sends the following message:




I have chosen a natural number $N$. All I can tell you is that an ITTM indexed by $N$ clocks some ordinal $alpha$. You can send me any real number that encodes any ordinal, and I will immediately tell you whether this ordinal is equal to $alpha$ or not. You have an infinite amount of infinitely powerful computational resources and infinite amount of time. Moreover, if you send me any countable set $S$ of ordinals, I will send you a number $0$ if this set does not contain $alpha$; otherwise, I will send you a positive number $i$ such that an $i$-th element of $S$ is equal to $alpha$. And here are three rules that must be taken into account: (i) any set $S$ that you send me is required to be a set of real numbers, where each element encodes an ordinal in a particular (fixed) way. It is your choice to fix such encoding, but you must tell me about your choice so that we can interpret all reals in the same way; (ii) If you send me a countable set (described in the previous rule), then (assuming that we agree on a fixed algorithm that decodes a single real number into a countable set of real numbers) you are required to provide an exact description of an algorithm (namely, an index of an ITTM together with a real number that encodes an ordinal for a stage when the output tape is expected to contain the real number that encodes the entire set $S$) that generates $S$; (iii) for any ITTM indexed by any natural number $n$, you are allowed to ask for a real number that appears on the output tape at stage $beta$, but if and only if you provide a real number that encodes an ordinal $beta$ (in the same fixed way that you have chosen). You can store these numbers in arbitrary (finite/infinite) sets/multisets and operate with them in any way you want.

So, if you find $alpha$, you win.




Question: does there exist a way to always win, no matter which $N$ the oracle chooses? If yes, then how?







logic automata ordinals turing-machines






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 30 '18 at 11:08







lyrically wicked

















asked Dec 28 '18 at 6:44









lyrically wickedlyrically wicked

20818




20818












  • $begingroup$
    Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
    $endgroup$
    – Noah Schweber
    Dec 29 '18 at 18:20












  • $begingroup$
    @NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 8:49












  • $begingroup$
    @lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:12












  • $begingroup$
    Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:42










  • $begingroup$
    @NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:52


















  • $begingroup$
    Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
    $endgroup$
    – Noah Schweber
    Dec 29 '18 at 18:20












  • $begingroup$
    @NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 8:49












  • $begingroup$
    @lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:12












  • $begingroup$
    Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:42










  • $begingroup$
    @NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
    $endgroup$
    – SSequence
    Dec 30 '18 at 9:52
















$begingroup$
Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
$endgroup$
– Noah Schweber
Dec 29 '18 at 18:20






$begingroup$
Just to clarify, you're essentially asking how we make sense of "the ITTM's situation (= what's on the tape, where the machine head is, and what state the machine's in) at stage $lambda$ on input $A$" when $lambda$ is a non-computable limit ordinal - is this correct?
$endgroup$
– Noah Schweber
Dec 29 '18 at 18:20














$begingroup$
@NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
$endgroup$
– lyrically wicked
Dec 30 '18 at 8:49






$begingroup$
@NoahSchweber: not exactly. The question is how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place. I edited the question to add a clarification.
$endgroup$
– lyrically wicked
Dec 30 '18 at 8:49














$begingroup$
@lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
$endgroup$
– SSequence
Dec 30 '18 at 9:12






$begingroup$
@lyricallywicked Your description in edit is a bit hard for me to follow. But when you wrote: "how to obtain a precise description (in the form of a real number) of a non-computable ordinal $lambda$ in the first place." I described how to obtain the "description"(as a real) of $omega_{CK}$ (which isn't computable) in my answer for example. But I am not fully clear on what the question is though. Maybe your question is more general or something like that etc. ..... for which I gave the link below the answer ..... which is quite advanced for me tbh.
$endgroup$
– SSequence
Dec 30 '18 at 9:12














$begingroup$
Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
$endgroup$
– SSequence
Dec 30 '18 at 9:42




$begingroup$
Actually, even though I don't understand what you wrote in edit, I have a guess regarding the intent of your question. I will modify my answer later on accordingly (based on what I think you are asking).
$endgroup$
– SSequence
Dec 30 '18 at 9:42












$begingroup$
@NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
$endgroup$
– SSequence
Dec 30 '18 at 9:52




$begingroup$
@NoahSchweber That would be a very good question I think (with some philosophical undertones). For example, in one of the questions I asked months ago $J_2$ was mentioned (link:arxiv.org/pdf/math/0509245.pdf). I don't understand what $J_2$ is, but it seems to be a very large value (based on strong closure properties apparently). So when powerful enough programs go beyond this, I have to admit I don't really understand what that would really "mean". But I suppose I am musing too much without knowing what I am talking about, so I will stop.
$endgroup$
– SSequence
Dec 30 '18 at 9:52










1 Answer
1






active

oldest

votes


















1












$begingroup$

It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.



Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).





First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).



Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.



Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.



The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).



After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.



Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).



Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.



Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.



Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.





Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)



I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.





Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.



Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).



It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.





My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.





EDIT:



As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.



Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).



The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.



To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:27












  • $begingroup$
    Also, there might be an added redundancy or two in the first construction I think.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:38










  • $begingroup$
    I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 11:02










  • $begingroup$
    @lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:25












  • $begingroup$
    At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:42













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

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%2f3054636%2fwhat-is-the-source-of-formal-descriptions-for-large-uncomputable-ordinals-clocka%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.



Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).





First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).



Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.



Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.



The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).



After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.



Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).



Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.



Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.



Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.





Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)



I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.





Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.



Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).



It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.





My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.





EDIT:



As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.



Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).



The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.



To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:27












  • $begingroup$
    Also, there might be an added redundancy or two in the first construction I think.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:38










  • $begingroup$
    I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 11:02










  • $begingroup$
    @lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:25












  • $begingroup$
    At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:42


















1












$begingroup$

It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.



Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).





First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).



Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.



Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.



The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).



After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.



Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).



Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.



Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.



Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.





Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)



I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.





Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.



Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).



It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.





My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.





EDIT:



As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.



Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).



The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.



To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:27












  • $begingroup$
    Also, there might be an added redundancy or two in the first construction I think.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:38










  • $begingroup$
    I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 11:02










  • $begingroup$
    @lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:25












  • $begingroup$
    At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:42
















1












1








1





$begingroup$

It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.



Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).





First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).



Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.



Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.



The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).



After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.



Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).



Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.



Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.



Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.





Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)



I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.





Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.



Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).



It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.





My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.





EDIT:



As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.



Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).



The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.



To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.






share|cite|improve this answer











$endgroup$



It's a good question. I will describe those specific aspects of the answer which I know about (but it will be a bit long though). There are very many aspects of course, of which I don't know much about.



Specifically though, I don't know much of anything about how models like $omega$ tape ITTMs handle this (that's why I will not try to describe how they handle this issue). So I will assume a more general model (such as ORM or extended tape ITTM).





First of all, one basic principle you can observe is that if you have access to well-order relation $lessequals:mathbb{N}^2 rightarrow {0,1}$ (for a well-order of $mathbb{N}$) of order-type $alpha$ then you can use it to halt a "little above" $alpha$. More specifically, given the access to the function $lessequals$, there will be some $beta geq alpha$ such that our given program halt at time $beta$. This isn't difficult (but not obvious at first though).



Before stating the process, let me first mention that all the steps below that have been described informally can indeed be checked by a powerful enough program model. First let $address:alpha rightarrow mathbb{N}$ be the (unique) order-preserving bijection(under the well-ordering relation) from $alpha$ to $mathbb{N}$. [I am not fully sure whether that's the best way to put it formally ... someone can correct this if I am wrong]. Now we define $address_{p}:p rightarrow mathbb{N}$ (where $p leq alpha$) to denote the restriction of the address function.



Now suppose that you are given an entirely arbitrary function $f:mathbb{N} rightarrow {0,1}$. Note that we don't even have to know before-hand whether $f$ is a well-order relation (for some well-order of $mathbb{N}$). The thing is that we can do both of the following at once: (1) We can check whether $f$ codes a well-order or not. (2) If the answer to (1) is yes, then suppose $f$ codes a well-order of order-type $alpha$. Then our program will halt just above $alpha$.



The first thing that we check is whether $f$ linear order on $mathbb{N}$ (https://en.wikipedia.org/wiki/Total_order). One can observe here is that in a program-like model you can just check each individual property in about $omega$ time (and hence all three of them in about $omega cdot 3$ time).



After this the main idea is to form the function $address_p:p rightarrow mathbb{N}$ in stages, until the stage $alpha$. First let's denote $range(address_p)=A_p$ and $B_p=mathbb{N}-A_p$ for the sake of convenience/brevity. Initially we have $A_0=phi$. Our first question is: what's the value $address(0)$? We basically check all the elements in $x in B_0$ one by one. We want to check whether $f(x,y)$ is true for all elements $y in B_0(=mathbb{N})$ and furthermore check whether $f(x,z)$ is false for all elements $z in A_0(=phi)$.



Now there are two different things that could happen. (i) We can't find any $x in A_0$ which satisfies the above requirement. (ii) We can find an $x in A_0$ which satisfies the above requirement. If (i) happens to be true, then the program can simply return "the given $f$ doesn't code a well-order". If you observe a bit closely the truth of (i) implies an infinite descending chain. Now if (ii) happens to be true, then the element $a in B_0$ for which this was true we basically set $address(0)=a$ (re-call that we are building this function in stages) and $A_1=A_0 cup a$. You might object what happens if we get two different $a,b in B_0$(where $aneq b$) so that both satisfy the given condition (but this won't happen because of the condition of linear order satisfied by $f$).



Essentially the above template is what you follow through out the calculation. We have a counter variable $p$ which starts from $0$ and which we keep increasing. At any given stage we have already formed $address_{p}:p rightarrow mathbb{N}$, and hence also the sets $A_p$ and $B_p$. But the question is that when do we know when to stop?? The answer is simple, once we think about it a bit! We have to keep a check on the set $B_p$ at each value $p$. Once $B_p=phi$ we have actually formed the function $address:alpha rightarrow mathbb{N}$. In that case we stop after we observe this condition.



Note that we could also stop well before $B_p=phi$. But actually, this would ONLY happen if $f$ didn't code a well-order. If $f$ did code a well-order we would stop at some point $beta$ where $beta geq alpha$.



Finally, let me add a bit of explanation how, in a formal sense, this construction proceeds. In a formal sense, the idea is that since we have already shown $f$ to be a linear order on $mathbb{N}$, now we need to prove the lack of infinite descending sequences. And this is the main idea with the construction of the set $A_p$ in stages. In particular, for any arbitrary stage $p leq alpha$, if the program doesn't stop/halt at that stage then we can say: "There are no infinite descending sequences which use an element that belongs to $A_p$". In other words, for every infinite descending sequence $g:mathbb{N} rightarrow mathbb{N}$ [that is a function $g$ such that for all $n in mathbb{N}$, $g(n) neq g(n+1)$ and $f(g(n+1),g(n))=1$], we must have $range(g) cap A_p = phi$. We could go along and try to show this by (transfinite) induction I think.





Note that directly using construction above we can basically clock just above $omega_{CK}$. Since our model already has access to all partial recursive functions (of two variables), we first check which of these functions are total. So we basically have a set $C subseteq mathbb{N}$ which initially contains indexes for all programs which compute a function from $mathbb{N}^2$ to ${0,1}$. One by one we start picking an element $x in C$ and then try to check whether it codes a well-order or not. In either case, after we have checked that we remove that element $x$ from $C$. In this case again our main stopping/halting condition is to check $C=phi$. Some reflection will show that, in this manner, we will halt just above $omega_{CK}$. (I think one can also use an alternative method like I mentioned in one of my older questions Halting at Exact Time)



I think there could be another method in a sense. I am not really familiar with it, so I am not comfortable mentioning it in detail. Given what is mentioned in this question, one could just use the corresponding (recursive) ordering relation (right from the start of a program) to stop just beyond $omega_{CK}$. But I am simply not familiar with it so I would just stop at that.





Now coming to your main question, how do we clock above $omega^{CK}_{2}$ for example. You can basically store all pairs of the form $(x,y)$ (where $xin mathbb{N}$ and $y in omega_{CK}$) where $x$ is an index of a program coding a well-order and $y$ is the order-type of the corresponding well-order. This can just be done by using the first construction described in the answer.



Alternatively, you can also store all $(x,y)$ where $x in mathcal{O}$ and $y=|x|_mathcal{O}$. But the construction will be a bit different (basically similar to what I described in my question above).



It is obvious that we can use any of the above collections to form a well-order of $mathbb{N}$ with order-type $omega_{CK}$. But now our infinite program can easily form a collection of all ordinary programs with access to the well-order relation for $omega_{CK}$. And much in the same way as before, this can be used to stop above $omega^{CK}_{2}$ for example.





My knowledge is a quite limited so I don't know/understand the full extent. Though this can vary depending on specific model you use. You would usually find it in relevant papers though, I think.





EDIT:



As far as I can guess, what you are asking is that if $alpha$ is a clockable ordinal, then can find a function $f:mathbb{N}^2 rightarrow {0,1}$ that can serve as a well-order relation for well-order of $mathbb{N}$ with order-type $alpha$. Once again I will assume a program style model (with variables with free range) .... mostly only because of familiarity reason.



Suppose some program starting from empty state halts at stage $alpha+1$. And now we want to write the "description" of $alpha$ as a real. First we set a variable equal to $alpha$ (which we can do easily). Then we simulate all programs (not ordinary ones, the ones from our general model) from empty input (using dovetailing etc.). Observe that this kind of simulation is indeed possible. Initially set $C=mathbb{N}$. When a given program reaches stage $alpha$ without halting it is excluded/removed from the simulation (and hence from $C$). When a program with index $x in mathbb{N}$ halts at time $t<alpha$ we add the pair $(x,t)$ in some main list $L$ (and also remove $x$ from $C$).



The above routing halts when $C=phi$. Indeed the routine will halt at some point (though it needs a bit of pondering), most importantly because we don't allow any program to run for more than $alpha$ time. And once you look carefully enough, the list $L$ can be used to describe the real which codes $alpha$. For example, if $L$ included for some $beta<alpha$, three different elements $(10,beta)$,$(14,beta)$,$(18,beta)$ then we just keep $(10,beta)$. Hence we have the well-order relation for well-order of a subset of $mathbb{N}$ with order-type $alpha$. This can easily be converted to obtain the relation for a well-order of $mathbb{N}$.



To make sure that the above construction works we need to prove that whenever the code $f:mathbb{N}^2 rightarrow {0,1}$ for a well-order of order-type $alpha$ is writeable, then so is code $g:mathbb{N}^2 rightarrow {0,1}$ for a well-order of any order-type $beta<alpha$. For this, consider the program that starts from empty input and gives us $f$. Now even an ordinary program can be used to obtain $g$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Dec 30 '18 at 12:29

























answered Dec 28 '18 at 10:04









SSequenceSSequence

55528




55528












  • $begingroup$
    For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:27












  • $begingroup$
    Also, there might be an added redundancy or two in the first construction I think.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:38










  • $begingroup$
    I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 11:02










  • $begingroup$
    @lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:25












  • $begingroup$
    At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:42




















  • $begingroup$
    For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:27












  • $begingroup$
    Also, there might be an added redundancy or two in the first construction I think.
    $endgroup$
    – SSequence
    Dec 28 '18 at 10:38










  • $begingroup$
    I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
    $endgroup$
    – lyrically wicked
    Dec 30 '18 at 11:02










  • $begingroup$
    @lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:25












  • $begingroup$
    At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
    $endgroup$
    – SSequence
    Dec 30 '18 at 11:42


















$begingroup$
For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
$endgroup$
– SSequence
Dec 28 '18 at 10:27






$begingroup$
For the comment towards the end of answer, perhaps this link might be good as a reference (advanced but probably good for the long term): mathoverflow.net/questions/159907.
$endgroup$
– SSequence
Dec 28 '18 at 10:27














$begingroup$
Also, there might be an added redundancy or two in the first construction I think.
$endgroup$
– SSequence
Dec 28 '18 at 10:38




$begingroup$
Also, there might be an added redundancy or two in the first construction I think.
$endgroup$
– SSequence
Dec 28 '18 at 10:38












$begingroup$
I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
$endgroup$
– lyrically wicked
Dec 30 '18 at 11:02




$begingroup$
I can imagine generating relatively small uncomputable ordinals, but I am not sure how this will work for very large recursively inaccessible ordinals... Note that if any ordinal is clockable, we must obtain its formal description somehow; otherwise, we cannot even refer to a stage that corresponds to the ordinal.
$endgroup$
– lyrically wicked
Dec 30 '18 at 11:02












$begingroup$
@lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
$endgroup$
– SSequence
Dec 30 '18 at 11:25






$begingroup$
@lyricallywicked It might depend on what you mean by "relatively small" though. You can use a similar method to what I described to reach $omega^{CK}_{omega}$ or $omega^{CK}_{omega^1_{CK}}$ for example.
$endgroup$
– SSequence
Dec 30 '18 at 11:25














$begingroup$
At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
$endgroup$
– SSequence
Dec 30 '18 at 11:42






$begingroup$
At any rate, it seems that what you are asking is: "if $alpha$ is clockable then can we obtain the description of $alpha$ as a real." The answer is yes. I will edit soon.
$endgroup$
– SSequence
Dec 30 '18 at 11:42




















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%2f3054636%2fwhat-is-the-source-of-formal-descriptions-for-large-uncomputable-ordinals-clocka%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

Probability when a professor distributes a quiz and homework assignment to a class of n students.

Aardman Animations

Are they similar matrix