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
7 votes
0 answers
311 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 ...
Noah Schweber's user avatar
5 votes
1 answer
938 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 ...
Ioannis Souldatos's user avatar
4 votes
0 answers
239 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 ...
Fedya's user avatar
  • 924
3 votes
0 answers
320 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}$, ...
Sam Sanders's user avatar
  • 3,901
2 votes
1 answer
147 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 ...
David J. Webb's user avatar
0 votes
0 answers
105 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\...
Ben Tom's user avatar
  • 107
11 votes
2 answers
518 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 ...
Timothy Chow's user avatar
  • 78.1k
1 vote
0 answers
106 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)...
abrahimladha's user avatar
3 votes
0 answers
190 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 ...
Johan's user avatar
  • 501
5 votes
1 answer
309 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 $\...
Ivan Meir's user avatar
  • 4,782
1 vote
1 answer
457 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 ...
H.C Manu's user avatar
  • 733
3 votes
1 answer
164 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)$ ...
Manlio's user avatar
  • 302
4 votes
1 answer
193 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 ...
Mark's user avatar
  • 118
5 votes
0 answers
283 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 ...
Jason Zesheng Chen's user avatar
4 votes
1 answer
412 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 ...
Léreau's user avatar
  • 211
6 votes
2 answers
672 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 ...
H.C Manu's user avatar
  • 733
5 votes
1 answer
259 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)...
James Hanson's user avatar
  • 10.3k
7 votes
0 answers
207 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 ...
Chain Markov's user avatar
  • 2,618
0 votes
1 answer
291 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-...
Thomas Benjamin's user avatar
2 votes
1 answer
194 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 α? ...
Reflecting_Ordinal's user avatar
5 votes
1 answer
193 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 ...
Peter Gerdes's user avatar
  • 2,551
25 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 ...
Peter Gerdes's user avatar
  • 2,551
4 votes
1 answer
326 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 ...
Gro-Tsen's user avatar
  • 29.9k
-4 votes
1 answer
568 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 ...
Thomas Benjamin's user avatar
2 votes
1 answer
101 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 ...
Forrest Jablonski's user avatar
2 votes
0 answers
164 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 ...
user400188's user avatar
13 votes
3 answers
806 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
147 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 ...
XL _At_Here_There's user avatar
0 votes
0 answers
199 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: ...
Wlod AA's user avatar
  • 4,686
4 votes
0 answers
205 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 \...
Noah Schweber's user avatar
3 votes
1 answer
179 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 ...
Reflecting_Ordinal's user avatar
4 votes
1 answer
416 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 ...
lyrically wicked's user avatar
1 vote
1 answer
276 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 ...
Thomas Benjamin's user avatar
1 vote
1 answer
252 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 ...
Noah Schweber's user avatar
5 votes
0 answers
287 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 ...
Corey Bacal Switzer's user avatar
20 votes
1 answer
1k 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 ...
Andrej Bauer's user avatar
  • 47.7k
0 votes
0 answers
190 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)$: $\...
Thomas Benjamin's user avatar
6 votes
1 answer
400 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 ...
Arno's user avatar
  • 4,366
3 votes
1 answer
98 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\...
Bjørn Kjos-Hanssen's user avatar
20 votes
1 answer
1k views

Is "almost-solvability" of Diophantine equations decidable?

Say that a Diophantine equation is almost-satisfiable iff for each $n\in\mathbb{N}$ it has a solution mod $n$. Trivially genuine satisfiability over $\mathbb{N}$ implies almost-satisfiability, but the ...
Noah Schweber's user avatar
7 votes
0 answers
293 views

Which countable ordinals are "Barwise compact" for $\mathcal{L}_{\infty,\omega_1}$?

Barwise compactness says (as a special case) that whenever $\alpha$ is countable and admissible, $T\subseteq\mathcal{L}_{\infty,\omega}\cap L_\alpha$ is $\alpha$-c.e., and every subset of $T$ which is ...
Noah Schweber's user avatar
7 votes
0 answers
453 views

Infinite time Turing machines, semi-decidable sets and descriptive set theory

Definition A set of reals $A$ is said to be ittm-eventually-semi-decidable if there is an Infinite Time Turing Machine programme $P_e$ so that $x\in A$ iff $P_e(x)$ has converged on “1” on its ...
Philip Welch's user avatar
  • 4,919
4 votes
3 answers
378 views

Countably infinite sets of ordinals as parameters for Ordinal Turing Machines

Let $A$ and $B$ denote two countably infinite sets of ordinals. Let $W_A$ denote the supremum of ordinals writable by Ordinal Turing Machines with the set $A$ given as the source of parameters. That ...
lyrically wicked's user avatar
9 votes
0 answers
283 views

Coding third-order objects via second-order ones

As is well-known, the language of second-order arithmetic only has variables for natural numbers and sets of natural numbers. Higher-order objects, like functions on $\mathbb{R}$, have to be ...
Sam Sanders's user avatar
  • 3,901
4 votes
1 answer
219 views

Is there a real $x$ which is eventually writable from an ordinal parameter $\alpha < \omega_1$, but not from $\omega_1$?

According to Lemma 3.14 in the paper “Recognizable sets and Woodin cardinals: Computation beyond the constructible universe”, there is a real $x$ in $L$ which is recognizable from some ordinal $\alpha$...
lyrically wicked's user avatar
3 votes
1 answer
225 views

Is there a $\Delta^0_2$ real with "easy total computability problem"?

This was asked at MSE without success. Granted, a bounty is still ongoing there, but it doesn't look like it will be answered. For (noncomputable) $A\subseteq\omega$ let $\tilde{A}=\{e: \varphi_e^A\...
Noah Schweber's user avatar
3 votes
0 answers
220 views

Bimodal determinacy logic for Borel games

This question is intended to be a first step towards answering this old question of mine. Let $K$ be the set of pairs $(\Sigma,\Pi)$ of quasistrategies, in the usual sense of games on $\omega$, for ...
Noah Schweber's user avatar
6 votes
1 answer
298 views

Given some recursive function, can we effectively associate it a polynomial as in the DPRM theorem?

I'm interested in the following assertion about the Davis-Putnam-Robinson-Matijasevich theorem Given a recursive function $f:\mathbb{N}\rightarrow\mathbb{N}$, i.e. its index, we can effectively get ...
Niconar's user avatar
  • 75
3 votes
1 answer
147 views

Analytic sets and Turing determinacy

I wonder whether the following question have a positive answer within $ZFC$. Question If $\{A_n\}_{n\in \omega}$ is a sequence of analytic sets so that $\bigcup_n A_n=2^{\omega}$, then there must be ...
喻 良's user avatar
  • 4,191
7 votes
0 answers
243 views

Computability assertions for Riemann zeta zeros

While looking for information about the Riemann zeta function, I kept running into the claim that there is an algorithm to decide whether or not a zero of the function is off the half-line. Is this ...
Pace Nielsen's user avatar

1 2 3
4
5
20