0
$\begingroup$

A set like for instance the ordered set with all even numbers first, followed by all odd numbers like ${\{0,2,4,...,1,3,5,...\}}$ is a computably enumerable set?

From wikipedia:

In computability theory, a set S of natural numbers is called computably enumerable >(c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.

Or, equivalently,

There is an algorithm that enumerates the members of S. That means that its output is simply a list of all the members of S: s1, s2, s3, ... . If S is infinite, this algorithm will run forever.

From a cardinal perspective is enumerable, in the sense there is a bijection between natural numbers and this particular set, so this particular bijection is a computation that enumerate their elements.

But can I provide a computation that outputs the numbers in the order I want? It seems that is not posible because the Turing machine would output even numbers forever, before having the opportunity to write an odd one...

Any countable ordinal is computably enumerable as a set?

$\endgroup$
5
  • 4
    $\begingroup$ This question doesn't make any sense - a set doesn't come with a fixed ordering. In other words, $$\{0,2,4,...,1,3,5,...\}$$ is just a silly way to write $\mathbb{N}$, and that's obviously computable. $\endgroup$ Jul 22, 2022 at 20:15
  • $\begingroup$ I miss that there is the concept of "computable ordinal" that is diferent from the "computably enumerable" one. $\endgroup$
    – Eduard
    Jul 22, 2022 at 21:58
  • $\begingroup$ I see... what I write down is not only a set. It is an structure consisting of $\mathbb{N}$ and a particular order. An structure by itself doesn't have a concept of being "computable". One can consider the computability of the underlying set or the computability of the relation that comes with that structure if they have one (like well order relation) ,... Agreed that question doesn't make sense at all. $\endgroup$
    – Eduard
    Jul 23, 2022 at 5:55
  • 2
    $\begingroup$ I wouldn't say that the question makes no sense at all, but yeah, you are confusing the computability of a set with the computability of the relation on the set (in this case a linear order), or any kind of additional structure. In this example you can easily guess that the structure is computable, but of course there are non-computable linear orders, or all kinds of weird things. $\endgroup$
    – Manlio
    Jul 24, 2022 at 8:37
  • $\begingroup$ I guess your last question is asking if for every countable ordinal, there's some computably enumerable relation on $\mathbb N$ that has that order type - this is false, for example the Church-Kleene ordinal $\omega_1^{CK}$ is countable and is a counterexample. $\endgroup$
    – C7X
    Aug 3, 2022 at 18:41

1 Answer 1

1
$\begingroup$

As mentioned in the comments, due to the axiom of extensionality sets have no order, in this case $\{0,2,4,6,8,\ldots,1,3,5,7,\ldots\}$ is equal to $\mathbb N$ since it contains exactly the same members as $\mathbb N$. If we pick a linear order $\prec$ where $0\prec 2\prec 4\prec\ldots 1\prec 3\prec 5\prec\ldots$, this is indeed computably enumerable via the first definition. We can show this using the following algorithm, accepting a pair of numbers as input:

def ordering(a,b):
  if (a mod 2) == (b mod 2):
    if a < b:
      return true
    else:
      loop forever on this line
  else:
    if (a mod 2) < (b mod 2):
      return true
    else:
      loop forever on this line

If we input a pair $(a,b)$ into this program, it halts if and only if $a$ precedes $b$ in our ordering, otherwise it never halts. So this is a semi-decision procedure for our ordering.

A more pure application of this is using a pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$: if we fix some (computable) pairing function, we may now input a pair of natural numbers in the form of one number, unpack the encoded input, and run the above algorithm. In fact, this also allows us to use the "enumeration" definition of recursive enumerability - there's a program that outputs all encodings of pairs $(a,b)$ where $a$ precedes $b$ in our ordering. In other words, this latter program outputs all naturals $x$ such that $\pi^{-1}(x)$, the unpacking of $x$, is a pair $(a,b)$ where $a\prec b$.


Edit: By request, here is more about a program outputting the encoded pairs:

def unpair(n): # Takes n and unpairs it, in terms of Cantor's pairing π : NxN -> N
  w = math.floor((math.sqrt(8*z+1)-1)/2)
  t = w*(w+1)/2
  return [w-n+t, n-t]
n = 0
while true: # Start enumerating numbers
  a = unpair(n)[0] # First entry
  b = unpair(n)[1] # Second entry
  if ordering(unpair(x)[0], unpair(n)[1]): # If n encodes pair:
    print(n)
  n += 1

The technical details of unpair don't matter that much, using any other bijective pairing function $\pi:\mathbb N\times\mathbb N\to\mathbb N$ also works, mainly then the answer to the question "what order does this program output pairs in?" changes. For this choice of $\pi$, these are some of the first numbers outputted along with the pairs they code:

  • 2, (0,1)
  • 5, (0,2)
  • 7, (2,1)
  • 9, (0,3)
  • 13, (1,3)
  • 14, (0,4)
  • 16, (4,1)
  • 18, (2,3)
  • ...
$\endgroup$
6
  • $\begingroup$ Thanks a lot. Nice to have the detailed answer with a concrete algorithm showing the computability of the relation. But still there is something I don't get at all. When intuitively thing about a computable enumeration I think $a_1, a_2, a_3,...$ where all elements are listed one by one by a single program in one single run. Is that wrong (especially for infinite sets)? $\endgroup$
    – Eduard
    Aug 27, 2022 at 18:07
  • $\begingroup$ In which order the "program that outputs all encodings of pairs (a,b)" would write the values? In general, roughly speaking, is that we can enumerate all elements, but not in any order we want? It is like the computability requirement only allows one single potential $\omega$ $\endgroup$
    – Eduard
    Aug 27, 2022 at 18:14
  • 1
    $\begingroup$ @Eduard A TM can't run for transfinite time, but if we look at this relation it has order type $\omega2$. Yet because $\omega2$ bijects onto $\omega$ via the pairing function, we can output the entirety of the information of $\prec$ without having to run a TM for transfinite time, as long as we output the info "out of order" (intuitively out of order, i.e. up to rearrangement). I can edit the answer to include what such a machine would look like but it might be best to not give any details for $\pi$'s definition $\endgroup$
    – C7X
    Aug 27, 2022 at 20:25
  • $\begingroup$ I find amazing how "easy" we can do transfinite induction when doing mathematics, like counting to $\omega$ and then adding one, or state such power set exists, and at the same time accept our computability limitations, turing-church tesis. $\endgroup$
    – Eduard
    Aug 28, 2022 at 21:04
  • $\begingroup$ I love ZFC. I consider it a great human achievement, but at the same time looks like witchery $\endgroup$
    – Eduard
    Aug 28, 2022 at 21:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .