# Tag Info

## Hot answers tagged computability

3

Yes, there is a c.e. set of Turing degree ${\bf 0}'$ all of whose noncomputability witnesses have Turing degree $\geq_T {\bf 0}'.$ Pick a pairing function $p:\omega\times\omega\to\omega.$ Let $\Sigma:\omega\to\omega$ be the busy beaver function. Take $X$ to be the set of $p(i,j)$ with $j\leq \Sigma(i).$ So $X$ is c.e. and has Turing degree ${\bf 0}'.$ Given ...

3

There's an empty function of each arity: specifically, the empty function of arity $n$ is the partial function $e^n: \subseteq\mathbb{N}^n\rightarrow\mathbb{N}$ whose domain is $\emptyset$. Put another way, its graph $\{(a_1,...,a_n, b): e^n(a_1,...,a_n)\downarrow=b\}$ is $\emptyset$, where "$\downarrow=$" means "is defined and equal to." ...

2

If both $B$ and $C$ were to be recursive, then their characteristic functions $\chi_B$, and $\chi_C$ would be recursive, and thus since $\chi_A = \chi_B + \chi_C$ plus the fact that recursive functions are closed under addition, $\chi_A$ would be recursive and therefore $A$ too. When saying $\chi_A = \chi_B + \chi_C$ I used the fact that $B \cup C = A$ and ...

2

Your judgement is correct, at least one of B or C must be non-recursive, since recursive sets are closed under (finite) union. This is fairly simple to prove, as given a procedure for deciding B and a procedure for deciding C, one can create a procedure for deciding B union C = A that is simply to run the procedure for B and the procedure for C, and return ...

2

Yes, your idea is correct. For $P = \lambda xy.M(Nxy)$ (I renamed the term $P$ to avoid confusion with $F = \lambda xy.y$), you have to consider all the possible applications to two booleans (which are $T$ and $F$), i.e. you have to consider the terms $PTT$, $PTF$, $PFT$ and $PFF$, and $\beta$-reduce them to their normal forms, which are still booleans. In ...

2

No, not at all. Let $f$ be any binary sequence whatsoever and let $g(2n)=f(n), g(2n+1)=0$. Then $g$ is not Martin-Lof random but $\{x:g(x)=1\}$ is exactly as complicated as $\{x:f(x)=1\}$. Non-randomness is not a simplicity condition. Or, put another way, complexity does not imply randomness. (For an extreme type of example of highly-complex but highly-...

2

The most natural way to prove this, in my opinion, is via the "syntactic" approach to computability. Specifically, use the following results: Fact 1: If $\theta(x_1,...,x_n)$ is $\Delta^0_0$ (that is, only uses bounded quantifiers), then the function t_\theta(x_1,...,x_n)=\begin{cases} 1&\mbox{ if }\theta(x_1,...,x_n),\\ 0&\mbox{ ...

2

Your suspicion is right - continuity in your sense, which I'll call "ce-continuity" to avoid confusion, does not imply computability. For example, we have the following: There is a total injective function $f:\mathbb{N}\rightarrow\mathbb{N}$ such that for every c.e. $X$ either $f^{-1}(X)$ is finite or $f^{-1}(X)$ is cofinite. Call such a function ...

2

The result shown by Mikrokosmos is correct. It is not true that $GTT$ $\beta$-reduces to $\lambda xy.xyxTT$. Let us see why. It is true that $N = \lambda xy.xyx$ represent the logical connective $\mathit{AND}$. Indeed, \begin{align} Txy &= (\lambda x'y'.x')xy &&& Fxy &= (\lambda x'y'.y')xy \\ &\to_\beta (\lambda y'.x)y &&&...

1

It is true that $S S (SK)$ you cannot apply any rule of the $SKI$-calculus because, as you correctly said, you do not have enough arguments. But you can feed $S S (SK)$ with enough arbitrary arguments (i.e. variables), to see how it behaves, and so you can give a "functional definition" of $S S (SK)$ (in the style of the other rules of the $SKI$-...

1

Suppose that $A$ were recursively enumerable. Define $h(x) = 0$, and define $g$ such that $\phi_{g(x)} = h \circ \phi_x$. Then $g$ is recursive, $\phi_{g(x)}(n) \downarrow$ iff $\phi_x(n) \downarrow$, and whenever $\phi_{g(x)}(n) \downarrow$, we have $\phi_{g(x)}(n) = 0 \leq 2021$. Then consider the set \$B = \{x \in \mathbb{N} | \forall n \in \mathbb{N}, \...

1

If we interpret "(basic) mathematics" as being a human model of various things about "the real world", there is scant reason to believe that taking that basic math to any logical extreme is necessarily a correct indicator of anything at all. Nevertheless, "of course", (some) human beings are interested in how their mental models ...

1

Definitely not, you could not do this without some sort of extra special bit of reasoning. Just because a counter-example might be incomprehensibly large, and algorithmically impossible to produce, the very fact a counter-example exists out there in the abstract world of Mathematics will have very dire and huge consequences. For example, the majority of real ...

1

There is a conjecture: There is no sequence of n consecutive positive integers which contains more primes than the sequence of integers from 2 to n. That's the second Hardy-Littlewood conjecture. And it seems intuitively true, since primes get more and more rare as numbers get larger. But a lengthy calculation (I mean hours but not days of CPU time) shows ...

1

According to https://www.cc.gatech.edu/~rpeng/CS4510_F18/Nov12Reductions.pdf: "Recall that a language L is Turing recognizable if there is a Turing machine that accepts exactly the words in L, but can either reject or loop indefinitely on an input that’s not in L." So just construct a TM that accepts 0, 11, and some other string, but rejects ...

1

Based on the lack of reference provided here and at MO, as well as my own lack of success in finding a reference, I'm going to tentatively say that this particular approach has not appeared as such in print. I'll delete this answer of course if someone supplies a reference in which it appears, but I think at present it's appropriate to move this off the ...

Only top voted, non community-wiki answers of a minimum length are eligible