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.
974
questions
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 ...
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 ...
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 ...
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}$, ...
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 ...
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\...
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 ...
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)...
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 ...
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 $\...
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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
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)...
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 ...
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-...
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 α? ...
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 ...
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 ...
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 ...
-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 ...
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 ...
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 ...
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 ...
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: ...
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 \...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)$:
$\...
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 ...
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\...
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 ...
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 ...
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 ...
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 ...
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 ...
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$...
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\...
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 ...
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 ...
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 ...
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 ...