0

What's the $e^{th}$ partial recursive function?

It refers here to the $e^{th}$ partial recursive function. Since no reference is provided, the reasonable implication seems to be that there's a canonical ordered set of such functions.

Andrés E. Caicedo
  • 79,201
it's a hire car baby
  • 9,243

1 Answers1

2

It is trivial to computably enumerate the partial recursive functions. Any such enumeration will do, and there is clearly no canonical sequence. No reference is provided because it is an extremely basic concept in computability theory. Same if you see phrases like "$k$-th program" or "$k$-th Turing machine".

user21820
  • 57,693
  • 9
  • 98
  • 256
  • I guess it's talking about any arbitrary enumeration of these then: https://ncatlab.org/nlab/show/partial+recursive+function ? – it's a hire car baby Dec 26 '19 at 11:12
  • @samerivertwice: I must warn you that ncatlab.org is full of errors, and even articles with no errors are rather useless for most purposes since they are written by a handful of people with an unhealthy narrow focus on a certain kind of 'logic'. If you want to learn logic, you should start with a standard text like the ones I recommended to you before. Most theorems about computable functions do apply to any computable enumeration of them, and there is no reason to care about a specific enumeration. One should in fact be wary if some theorem relies on a specific enumeration. – user21820 Dec 26 '19 at 13:29
  • In any case, if you have basic programming knowledge, then you should know that it's trivial to enumerate all valid programs in a Turing-complete language (such as Python), and that there are some nice enumerations (like ordered by length-lexicographic order) but no distinguished one in any sense that reasonably pertains to the abstraction of computation. – user21820 Dec 26 '19 at 13:32
  • Thanks for the heads up. FWIW the Collatz graph (assuming true) assigns a bijection between the integers and a subset of the ordinals smaller than $\omega^\omega$. I was curious about how membership of this subset relates to membership of Kleene's $\mathcal O$, if at all. There are a lot of similarities and this possibility if true would put the 5-rough numbers in bijection with the limit ordinals in Kleene's $\mathcal O$. If you were willing to chat we could quickly determine if this is possible. – it's a hire car baby Dec 26 '19 at 14:08
  • @samerivertwice: Sorry, but you are not talking any sense regarding the Collatz conjecture. It is absolutely unrelated to computable ordinals, and has no link with $ω^ω$ either. I am not willing to discuss anything about the Collatz conjecture because it is a waste of time. – user21820 Dec 26 '19 at 14:11
  • Your last but one statement is untrue about there being no link to $\omega^\omega$. Let $w^{<\omega}$ be the set of finite strings of natural numbers $x_n,x_{n-1},\ldots x_0$ . Then let these $x_i$ enumerate the number of divisions by $2$ between each $3x+1$ in the Collatz graph of any given integer e.g. $3,10,5,16,8,4,2,1\mapsto 1,4_{\omega^{<\omega}}$. Then if the Collatz conjecture is true, every integer has a unique sequence of integers associated with it. Writing in Cantor normal form $\sum_i \omega^i\cdot x_i$ completes the bijection from positive integers to a subset of $\omega^\omega$ – it's a hire car baby Dec 26 '19 at 14:20
  • You are making a meaningless conflation. "$ω^{<ω}$" is defined as something completely unrelated to ordinals....... – user21820 Dec 26 '19 at 14:22
  • I explicitly give the bijection from $\omega^{<\omega}$ to a subset of $\omega^\omega$ in the last sentence. Moreover if you then want the transfer of structure from the Collatz conjecture to the ordinals, the Collatz function $3x+1$ truncates the ordinals while division by $2$ reduces the coefficient of the term $\omega^0$. – it's a hire car baby Dec 26 '19 at 14:23
  • @samerivertwice: For the last time, there is absolutely no relation. Clearly, you have severe misconceptions about ordinals. Your claim that $ω^{<ω}$ is related to ordinals is as meaningless as saying it is related to rationals just because I can produce a bijection between them. Just no. – user21820 Dec 26 '19 at 15:11
  • I said that if the Collatz conjecture was true it led to a bijection from the natural numbers to a subset of $\omega^\omega$. You said I wasn't talking any sense and that there was no link between the two - statements which I refuted. I respect your right not to discuss it but as long as you continue make untrue and unjustified claims that people are talking nonsense you are likely to keep getting into scrapes. – it's a hire car baby Dec 26 '19 at 15:16
  • You have the cheek to make unjustified claims despite the fact that I am familiar with logic and you are not. Please do not ping me anymore if you don't actually want to learn why you are wrong. – user21820 Dec 26 '19 at 15:22
  • If I am wrong then I would like to learn why. At the moment I do not believe I am wrong but my mindset is always open to a counterargument - always. – it's a hire car baby Dec 26 '19 at 15:24
  • You claim to have statements C,X where X involves ordinals, and a proof that C implies X, but that does not at all imply that ordinals have any relevance to C whatsoever. And as a logician I can tell you that your "C implies X" is a logical triviality that anyone with basic knowledge about ordinals can concoct, so there really is nothing intrinsically relating C to ordinals. – user21820 Dec 26 '19 at 15:25
  • In my view I have statements $C,D,X$ where $X$ involves ordinals and I state "if and only if $D$ then $C\iff X$". Then I propose to discuss whether $C\iff X$ looks on a prima facie basis to have any merit. – it's a hire car baby Dec 26 '19 at 15:28
  • @samerivertwice: It doesn't matter the specific form. It is a logical triviality to concoct the kind of statements you are coming up with. I can clearly see that you think it is a great deal but that's because you don't have sufficient grasp of basic logic to be able to see the intrinsic logical structures and connections, and so you think something is great and important even when it brings absolutely no insight into the actual structure. – user21820 Dec 26 '19 at 15:33
  • No, I don't think it has great importance. What I see is two objects having a structure in common. – it's a hire car baby Dec 26 '19 at 15:35
  • You believe you see. But no, there is nothing at all in the structure of the ordinals that has anything to do with the Collatz conjecture. When you have published a paper on the conjecture in AMS, come back to me and give me a link, and I guarantee you I will read it. Before that, I do not want to talk anymore about the Collatz conjecture, for the reason I stated. – user21820 Dec 26 '19 at 15:37
  • You claim they are logical trivialities. All I ever argued is that they were not nonsenses. It turns out we are in total agreement! – it's a hire car baby Dec 26 '19 at 19:26