0
$\begingroup$

A recursive set $Y$ is a set with a characteristic total computable function $\chi_Y$ so that $\chi_Y(n)=0$ iff $n\in Y$ and $\chi_Y(n)=1$ iff $n\notin Y$. Let a $recursive \ condition$ be one which defines a recursive set. Let a recursive condition $Q(n)$ for "is a rational number" be given. A totally computable real number is here taken as a natural number $\ulcorner M\urcorner$ which encodes a Turing machine M and such that for some recursive condition $A(x)$, $\ulcorner M\urcorner$ is the least natural number $(U(\mu zT(\ulcorner M\urcorner,z,x))=0\leftrightarrow Q(x)\wedge A(x))\wedge (U(\mu zT(\ulcorner M\urcorner,z,x))=1\leftrightarrow\lnot (Q(x)\wedge A(x))) $; it is presupposed that $Q(x)\wedge A(x)$ amounts to a Dedekind cut. For instance, the Turing Machine $g$ given by $(U(\mu zT(\ulcorner g\urcorner,z,x))=0\leftrightarrow Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)\wedge (U(\mu zT(\ulcorner g\urcorner,z,x))=1\leftrightarrow\lnot (Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)) $

prints $0$ if it is given the input of a natural number $x$ fulfilling the recursive condition $Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x$ and prints $1$ if it is given a natural number $x$ fulfilling the recursive condition $\lnot (Q(x)\wedge x<_\mathbf{Q}2\cdot_\mathbf{q}x)$ as input.

It is known by a result of Specker that bounded computable sets of computable real numbers do not always have a computable real number as a least upper bound. Is the situation different for totally computable real numbers as here so that recursive sets of totally computable real numbers with an upper bound have a least upper bound which is totally computable?

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ If you insist that $M$ be the least number with the given property, then it seems that any recursive set of totally computable real numbers must be finite, since given an infinite such set $S$, we can use the recursion theorem to build a TM with index $N$ that finds the least $M \in S$ greater than $N$, and then copies the TM with index $M$, contradicting the minimality of $M$. $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 25, 2017 at 20:15
  • 1
    $\begingroup$ Yes, if $S$ is an infinite recursive set of totally computable real numbers then the Turing machine coded by $N$ by definition computes exactly the same function as the one coded by $M$, and hence this is indeed a total computable function defining a recursive set. (Sorry, I've been using $M$ to mean the same thing as $\ulcorner M \urcorner$.) $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 25, 2017 at 21:43
  • 1
    $\begingroup$ Because $\ulcorner M \urcorner$ is chosen so that $\ulcorner M \urcorner > \ulcorner N \urcorner$. $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 25, 2017 at 22:44
  • 2
    $\begingroup$ Here's a more general version: Let $\Phi_e$ be the Turing machine with index $e$. Say that a natural number $e$ is a minimal index if there is no $i<e$ such that $\Phi_i$ computes the same function as $\Phi_e$. Then every computable set of minimal indices is finite. Here's the proof: Suppose $S$ is an infinite computable set of minimal indices. By the recursion theorem, there is a natural number $i$ such that $\Phi_i$ acts as follows: Let $e$ be the least number greater than $i$ in $S$. Then $\Phi_i(n)=\Phi_e(n)$ for all $n$. The existence of $i$ contradicts the minimality of $e$. $\endgroup$
    – Denis Hirschfeldt
    Commented Mar 25, 2017 at 23:09
  • 2
    $\begingroup$ To clarify the role of the recursion theorem in Denis' argument: suppose $S$ were an infinite computable set of minimal indices. Then (exercise) there is a total computable $f$ such that for all $i$, $f(i)$ is the least element of $S$ greater than $i$. Now apply the recursion theorem to $f$; we get a $c$ such that $\Phi_c\cong \Phi_{f(c)}$. OK, but then we know two things: (1) $f(c)$ is in $S$, and (2) $f(c)>c$. But this gives us a contradiction: each element of $S$ must be a minimal index, but $f(c)$ isn't since $c$ is a smaller index for the same partial computable function. $\endgroup$
    – Noah Schweber
    Commented Mar 26, 2017 at 3:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .