Questions tagged [computability-theory]

computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.

Filter by
Sorted by
Tagged with
1 vote
0 answers
107 views

Why are there no "natural" occurrences of high or low r.e sets?

The notions of a low and high sets were introduced, I think by Soare, in the context of the dense structure of degrees of those sets which are neither r.e. neither recursive. My question is: Why are ...
user avatar
  • 197
5 votes
1 answer
124 views

$\Pi^0_2$ singleton of minimal arithmetic degree?

Is it known if there is a $\Pi^0_2$ singleton of minimal arithmetic degree? To elaborate a bit, this is asking whether there is a non-arithmetic set $X$ such that for any $Y$ arithmetic in $X$ either ...
user avatar
  • 1,515
6 votes
2 answers
1k views

Does permission always work?

Suppose $g$ is a total computable injective function and $f$ is a total computable function satisfying $$g(x)<f(x)$$ for all sufficiently large $x$. Then we have $ran(f)\le_Tran(g)$; basically, ...
user avatar
4 votes
1 answer
101 views

Existence of an inseparable minimal pair

An inseparable minimal pair is a pair of sets $A, B \subseteq \mathbb{N}$ which are inseparable: there is no computable $C \subseteq \mathbb{N}$ such that $A \subseteq C$ and $B \subseteq \mathbb{N} \...
user avatar
  • 43.4k
6 votes
1 answer
128 views

How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?

Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
user avatar
  • 6,344
8 votes
2 answers
385 views

Comprehension axiom who helps in the opposite direction

Usually, having more comprehension axiom means the more you can prove. We wonder if the converse can be the case. Is there a natural problem $\mathsf{P}$ so that $\mathsf{P}+\neg(\Gamma-\mathsf{...
user avatar
  • 909
6 votes
0 answers
183 views

Fragments of infinitary logic with a weak definability property

For a countable admissible ordinal $\alpha$, let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ and let $\equiv_\alpha$ be the corresponding elementary equivalence relation. Say that ...
user avatar
4 votes
0 answers
75 views

Are there more learnable but undecidable cases except the halting problem

Per request, I cross post the question here which is original from math.stackexchange In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
user avatar
  • 141
2 votes
0 answers
112 views

Details on partial oracle computability in Ganov

I'm currently glancing at a couple papers by V. A. Ganov (Recursion on generalized computable ordinals and A generalized constructable continuum), and I'm running into some basic issues. Ganov ...
user avatar
2 votes
0 answers
76 views

Is there a nice characterization of degrees which compute no c.e.a. set?

Recall that a set $A$ is c.e.a. (computably enumerable in and above) if there is some $X<_T A$ such that $A$ is $X$-c.e. I am interested in degrees (specifically $\Delta^0_2$ degrees) that are not ...
user avatar
6 votes
0 answers
289 views

An uncountable structure with unusual "relatively-computable shadow"

Below, all structures are infinite and in a finite language. Given a structure $\mathcal{A}$ with domain $\omega$, we conflate $\mathcal{A}$ with some reasonable encoding of its atomic diagram for ...
user avatar
4 votes
1 answer
160 views

MIP^*=RE and quantum computation

I recently learned about the MIP^*=RE result. I have to admit that I don't understand big parts of this paper and I am barely familiar with quantum physics. I hope my questions below make sense. I ...
user avatar
4 votes
0 answers
203 views

Coefficients in Hilbert's tenth problem over number rings: do they matter?

Here are two ways to define Hilbert's tenth problem over a ring $R$: Given a polynomial $p \in \mathbb Z[x_1,\ldots,x_n]$, can one decide whether it has a solution in $R^n$? Given a polynomial $p \in ...
user avatar
  • 864
3 votes
0 answers
288 views

Different definitions of 'countable set'

There are a number of different definitions of 'countable set', all equivalent given a strong enough (classical) system. The obvious ones (injection to $\mathbb{N}$, bijection to $\mathbb{N}$, ...
user avatar
  • 1,859
2 votes
1 answer
127 views

Sets $A$ such that $A$-maximal sets are $\Delta^0_2$

Recall that $M\subseteq\omega$ is maximal if it is c.e., and can be only trivially extended by other c.e. sets, i.e. if $M\subseteq N$ and $N$ is c.e., then either $\overline{N}$ or $N\setminus M$ is ...
user avatar
0 votes
0 answers
82 views

Embedding of graph classes

Let $\mathfrak{G}$ be the class of all finite connected undirected graphs, $A,B \subseteq \mathfrak{G}$. Let $X[n]=\{G\in X :v(G)=n\}$, consider a function: $$KE_n(A,B)=\max_{G\in A[n]}\min_{G\...
user avatar
  • 65
11 votes
2 answers
484 views

Undecidability of irreducibility of infinite families of integer polynomials?

A recent question, Is irreducibility of polynomials $\in\mathbb{Z}[X]$ over $\mathbb{Q}$ an undecidable problem? was quickly answered in the negative. I am wondering if there is a simple example of a ...
user avatar
  • 64.1k
1 vote
0 answers
69 views

Jones–Sato–Wada–Wiens diophantine equation [closed]

I came across this from the 1993 book Matiyasevic - Hilbert's 10th problem. Typeset from another question: \begin{align} P(a,b,\dotsc,z)=(k+2)\Bigl(1&-(wz+h+j-q)^2\\ &-\left[(gk+2g+k+1)...
user avatar
3 votes
0 answers
162 views

Set-theoretic hierarchy using the uniqueness quantification

Has an equivalent of the set-theoretic hierarchies (arithmetical, hyperarithmetical, Levy etc.) that uses the uniqueness quantification, $\exists !$ (and its dual, $\neg\exists!\neg$) been studied ...
user avatar
  • 203
5 votes
1 answer
274 views

Is $\mathbb{Q}$ the orbit of a continuous function that is computable when restricted to $\mathbb{Q}$?

In the previous post What is the smallest set of real continuous functions generating all rational numbers by iteration? I asked for the smallest set of continuous real functions that could generate $\...
user avatar
  • 4,350
1 vote
1 answer
430 views

Church-Turing tests and quasi-computational models [closed]

What came to mind intuitively is what I would call C-T tests that are more or less methods of accepting some model as being a computational model or not. The question is in what amount and how could ...
user avatar
  • 197
2 votes
1 answer
134 views

Computing the halting problem with no computable bound on the use function

I would like to prove that there are two sets $A,B\subset \mathbb{N}$ such that $A |_T B$ $\emptyset' \equiv_T A\oplus B$ for every $e$, if $\{e\}^{A\oplus B}=\emptyset'$ then the map sending $(B,n)$ ...
user avatar
  • 193
4 votes
1 answer
169 views

Borel ranks of Turing cones

For a non recursive $x \in 2^{\omega}$, define $C_x = \{y \in 2^{\omega}: x \leq_T y\}$. Note that $y \in C_x$ iff $(\exists e)(\forall n)(\Phi^y_e(n) = x(n))$ where $\Phi_e$ is the $e$th Turing ...
user avatar
  • 118
5 votes
0 answers
266 views

What is known about when regularity properties only hold for partial boldface pointclasses?

Apologies in advance for a rather vague and open-ended question. Results about regularity properties of the projective pointclasses tend to have a wholesale flavor. By this I mean one tends to be ...
user avatar
3 votes
0 answers
308 views

Alternative proof of Tennenbaum's theorem

The standard proof of Tennenbaums's theorem uses the existence of recursively enumerable inseparable sets and is presented e.g. in Kaye [1, 2], Smith [3]. In the following, $\mathcal{M}$ will always ...
user avatar
  • 191
6 votes
2 answers
614 views

Relationship between non-standard computation and TM(oracle)?

We know that there are non-standard models of arithmetic, and in such models there are non-standard proofs of standardly unprovable sentences. Now, we can imagine a version of representability ...
user avatar
  • 197
5 votes
1 answer
209 views

Which arithmetical sentences have no counterexamples in the sense of Kreisel?

It is a well-known fact that given a first-order sentence $\psi$ in prenex normal form $\forall x_1 \exists y_1 \forall x_2 \exists y_2 \dots \forall x_n \exists y_n \theta(x_1,\dots,x_n,y_1,\dots,y_n)...
user avatar
  • 6,344
7 votes
0 answers
203 views

Is $E(G)$ recursively presented for finitely presented $G$?

Suppose $G$ is a group. Consider the set $G^G$ of all functions $G \to G$, which forms a group under elementwise multiplication. Now, for all $g \in G$ let’s define $c_g \in G^G$ as the constant ...
user avatar
  • 2,598
0 votes
1 answer
222 views

Can finite sets be non-c.e. depending on how they are presented?

I ask the question because of the following statement found in Mark Burgin's paper, "Algorithmic complexity of recursive and inductive algorithms", Theoretical Computer Science 317 (2004) 31-...
user avatar
2 votes
1 answer
123 views

Ordinal notations in α-recursion theory

Is there a theory about using α-recursion to compute ordinals? For example, consider α-recursive well orders on α, what is the supreme of their order type? Is it the next admissible ordinal after α? ...
user avatar
5 votes
1 answer
169 views

Does every cuppable r.e. set cup with a low set?

Remember, that an incomplete r.e. set $A$ is cuppable if there is an incomplete r.e. set $B$ such that $A\oplus B \equiv_T 0'$. It's relatively easy to build a low cuppable set but my question is ...
user avatar
  • 1,515
24 votes
2 answers
2k views

Decidability of 3 body problem

Is there a result showing that something along the lines of the three body problem is undecidable? Or are they known to be decidable or neither? I mean problems along the lines of the following ...
user avatar
  • 1,515
4 votes
1 answer
223 views

Is there a correspondence between principles of omniscience and computability classes?

My question will be speculative and therefore a little vague. I wonder if attempts have been made to define a correspondence between, on the one hand, limited principles of omniscience that can be ...
user avatar
  • 21.7k
-4 votes
1 answer
445 views

What is an oracle, really? [closed]

Regarding oracles, might this be a reasonable description of their inner workings (this from Hartley Rogers, Jr.'s text, Theory of Recursive Functions and Effective Computability)? Why should I ask ...
user avatar
2 votes
1 answer
76 views

information theoretic lower bound for hashing functions [closed]

The literature on minimal perfect hashing functions (mphf) says that the best function we can do will have to store $\frac1{\ln(2)}$ (~1.44) bits per key. There are some sets though that require 0 ...
user avatar
2 votes
0 answers
148 views

Is there an example Hamiltonian that is uncomputable?

In a paper from 2015 Toby S. Cubitt et al showed that the problem of determining the existence of a band gap in the excitation spectrum of a quantum many-body system, was undecidable. This result ...
user avatar
13 votes
3 answers
716 views

Undecidable infinite analogs of NP-complete problems?

In the paper Some undecidable problems involving edge-coloring of graphs, Burr proves that a certain k-coloring problems for certain infinite graphs (however, with finite descriptions - here "...
0 votes
1 answer
121 views

Is set of the indices of c.e.sets that cover a productive set also productive one?

Given a productive set, there is a collection of c.e. sets union of which is the productive set, as we know that every c.e. set is with a c.e. function with a index. My question: is the set of the ...
user avatar
0 votes
0 answers
191 views

The max output of 11-line long programs in Minsky computer language

Open Problem: What is the maximal maximal output of an 11-line Minsky program? (And could you prove that the output of that program is maximal among all 11-line Minsky programs). My own result is: ...
user avatar
  • 3,379
4 votes
0 answers
195 views

Is there a ${\bf 0'}$-computable linear order with "all intervals wild"?

Say that a linear order $L$ is a thicket iff $L$ is infinite, and for all elements $a,b,c_1,...,c_n\in L$ with $a<_Lb$ and $[a,b]_L$ infinite the following are equivalent: $\{a,b\}\subseteq \...
user avatar
3 votes
1 answer
144 views

How to use Manuel Lerman's framework of priority method as blackbox?

Manuel Lerman has a book "A Framework for Priority Arguments" that builds a framework of priority method. However, the definitions in the book are quite involved and not written in a very ...
user avatar
4 votes
1 answer
287 views

How large are the stabilization times of Ordinal Turing Machines with an oracle for the transfinite initial ordinals?

This question is based on the assumption that $V \ne L$ and we have $\omega_1^L < \omega_1$ (here $\omega_1^L$ is equal to the supremum of ordinals accidentally writable by no-oracle Ordinal Turing ...
user avatar
3 votes
0 answers
148 views

Building high scott rank structures via (restricted) ultraproduct over $\omega_1^{CK}$

For a limit ordinal $\alpha\le\omega_1^{CK}$ let $\mathcal{L}_{\alpha}=L_{\alpha}\cap\mathcal{L}_{\infty,\omega}$; in particular, $\mathcal{L}_{\omega_1^{CK}}$ is the usual hyperarithmetically-...
user avatar
0 votes
1 answer
191 views

Can $\{x \mathrel| \text{$\varphi_{x}$ total}\}$ be deemed a "lost melody" relative to classical recursion theory?

Consider the definition of "lost melody" given by Merlin Carl in his arXiv preprint, "The Lost Melody Phenomenon" (arXiv: 1407.3624v5 [math.LO] 16 Mar 2015): A lost melody is a ...
user avatar
1 vote
1 answer
225 views

Natural strong logic with Barwise compactness property

Throughout, by "logic" I mean regular logic (in the sense of Ebbinghaus–Flum–Thomas) whose sentences are coded by elements of $\mathsf{HC}$. Say that $\mathcal{L}$ is Barwise compact iff ...
user avatar
4 votes
0 answers
207 views

$\Sigma_n$-complete sets in the Levy hierarchy

Recall that a set $A \subseteq \mathbb N$ is (many-one, Turing) $\Sigma_n$-complete if it's $\Sigma_n$ and any other $\Sigma_n$ set (many-one, Turing) reduces to it. This definition actually makes ...
user avatar
17 votes
1 answer
972 views

Is the one-point compactification of $\mathbb{N}$ computably countable?

The one-point compactification $\mathbb{N}_\infty$ of $\mathbb{N}$ is obtained from the discrete space $\mathbb{N}$ by adjoining a limit point $\infty$. It may be identified with the subspace of ...
user avatar
  • 43.4k
0 votes
0 answers
175 views

Does the following characterization of the elements of $\mathscr P$($\omega$) fail for ITTM's?

Hartley Rogers Jr., on pg. 120 of his text, Theory of Recursive Functions and Effective Computability, presents and discusses the following characterization of the sets in $\mathscr P(\omega)$: $\...
user avatar
6 votes
1 answer
333 views

Computing the complex roots of a monic polynomial

The map from monic complex polynomials to the unordered tuples of their roots (each appearing according to its multiplicity) is computable. This seems to have been known for a long time, and with ...
user avatar
  • 3,356
3 votes
1 answer
88 views

Join-like operation and Medvedev reducibility

Let $\mathcal C, \mathcal D\subseteq 2^\omega$. Let $$ \DeclareMathOperator{\Either}{Either} \Either(\mathcal C,\mathcal D)=\{A\oplus B: \text{either }A\in \mathcal C, B\in\mathcal D\text{, or }B\...
user avatar

1
2 3 4 5
17