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
70 votes
2 answers
5k views

Will this Turing machine find a proof of its halting?

Consider the following Turing machine $M$: it searches over valid ZFC proofs, in lexicographic order, and if it finds a proof that $M$ halts, then it halts. If we fix a particular model of Turing ...
user avatar
  • 1,589
3 votes
0 answers
58 views

Extending the class of primitive recursive functions with higher order recursion schema

I'm trying to extend the class of primitive recursive functions by extending the recursion schema over higher types. We usually define the class of primitive recursive functions by using zero function,...
user avatar
  • 191
3 votes
1 answer
92 views

When does a clone on a two-element set have almost abelian symmetry groups?

Say that a clone (in the sense of universal algebra) $\mathfrak{C}$ has almost abelian symmetry groups (= aasg) iff for each function $f(x_1,...,x_n)\in\mathfrak{C}$ there is an abelian subgroup $A\...
user avatar
0 votes
1 answer
55 views

Non-isomorphic graphs with identical iterated degree matrix

If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$ Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \...
user avatar
2 votes
0 answers
146 views

The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals

This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty). The term “stabilization time of a machine” for this question implies the ...
user avatar
4 votes
1 answer
197 views

Existence of a particular function that maps an arbitrary set of ordinals to a single ordinal

Does there exist a function $f$ that satisfies all of the following three properties? The function converts an arbitrarily large (empty, finite, countably/uncountably infinite) set of ordinals to a ...
user avatar
1 vote
0 answers
50 views

When are normal forms computable in amalgamated produts and HNN extensions

I have had little luck searching for references on the following. I would thank a lot any reference. What are known conditions that ensure computable normal forms on amalgamated products and HNN ...
user avatar
  • 75
5 votes
1 answer
83 views

Computable functionals avoiding embeddings of linear orderings

Given a linear order $\mathcal{S}$, let $\mathbb{A}_\mathcal{S}$ be the class of all ordertypes which do not embed $\mathcal{S}$ (= do not have a suborder isomorphic to $\mathcal{S}$). Say that a ...
user avatar
2 votes
1 answer
118 views

Hard-to-"realize" instances of downward density

This question is motivated by a vague analogy between true paths in priority arguments and realizers - relative to an oracle - in the sense of intuitionistic logic. Intuitively, I'm looking for a ...
user avatar
3 votes
0 answers
152 views

Is this recursion theoretic analogue of a criterion of weakly compact cardinal true?

Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
user avatar
1 vote
1 answer
83 views

If $X \leq_T Y + 0'$ does there exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$?

If $X \leq_T Y + 0'$ does there always exist $Z \leq_T Y$, $Z \leq_T X$ with $X \leq_T Z'$? Obviously, we can find $Z \leq Y$ where the $y$-th column of $Z$ has a limit equal to $X(y)$. Just let $\...
user avatar
  • 1,615
8 votes
0 answers
282 views

How much downward density can we get without injury?

$\newcommand{\ran}{\operatorname{ran}}$This question is basically a riff on the first section of Maass' paper Recursively enumerable generic sets, with some rephrasing for readability. All results ...
user avatar
2 votes
0 answers
143 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
  • 317
6 votes
0 answers
160 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,615
7 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
116 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.8k
6 votes
1 answer
149 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,544
8 votes
2 answers
393 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
188 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
2 votes
0 answers
113 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
79 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
295 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
192 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
221 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
  • 874
3 votes
0 answers
297 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,879
2 votes
1 answer
129 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
85 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
495 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
  • 66.1k
1 vote
0 answers
72 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
167 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
  • 285
5 votes
1 answer
280 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,492
1 vote
1 answer
446 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
  • 317
2 votes
1 answer
140 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
172 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
268 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
1 answer
353 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
  • 201
6 votes
2 answers
623 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
  • 317
5 votes
1 answer
218 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,544
7 votes
0 answers
204 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
233 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
131 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
174 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,615
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,615
4 votes
1 answer
225 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
  • 22.4k
-4 votes
1 answer
455 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
77 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
151 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
726 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
123 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
193 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,655

1
2 3 4 5
17