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
2
votes
1answer
130 views

How to compare three supremums of ordinals eventually writable by Ordinal Turing Machines?

This question implies that we have fixed: (i) a particular enumeration of Ordinal Turing machines; (ii) a particular way to encode an ordinal by an infinite binary sequence. The class of $[1]$-...
6
votes
3answers
143 views

Relationship between provable in $RCA_0$ and effectively true

Question: What is the relationship between provability in $RCA_0$ and effectively true? In other words: Given a problem, if a statement asserting the existence of a solution of the problem is provable ...
3
votes
0answers
62 views

Empty preimage under homomorphism of finitely presented groups with decidable word problems

Let $G, H$ be finitely presented groups with decidable word problems. Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
11
votes
1answer
507 views

Does every countable set of Turing degrees have an upper bound, without AC?

It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
6
votes
0answers
227 views

Rational point oracle for smooth projective varieties

You have an oracle that decides if a smooth projective variety over $\mathbb{Q}$ has a $\mathbb{Q}$-point. Can you then algorithmically decide if an arbitrary variety over $\mathbb{Q}$ has a $\mathbb{...
4
votes
1answer
168 views

Is decidability reducible to unique decidability (perhaps in multilinear polynomial situations)?

Given a Diophantine equation it is not decidable if it has integer solution. I. Is there a Diophantine set $\mathcal D_{unique}$ satisfying the properties every member in $\mathcal D_{unique}$ is a ...
0
votes
0answers
81 views

Where does intuitionistic predicate logic live in the arithmetical hierarchy?

I started reading Plisko's papers on arithmetic complexity on the arithmetic complexity of constructive logic (see for example here or here). In this context, I started wondering about the following ...
2
votes
0answers
176 views

Can we have a “very strong” cone phenomenon in the Turing degrees (and a related question)?

By Borel determinacy + Martin's cone theorem, for every countable fragment $\mathcal{A}$ of $\mathcal{L}_{\omega_1,\omega}$ there is a turing degree ${\bf c}$ such that for all ${\bf d}\ge_T{\bf c}$ ...
6
votes
1answer
163 views

Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?

Recall that a structure $\mathcal{M} = \langle M, I^\sigma_M \rangle$ in a signature $\sigma$ is categorically axiomatized by a second-order theory $T$ when, for any $\sigma$-structure $\mathcal{N} = \...
4
votes
2answers
311 views

How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

Given a fixed enumeration of Infinite Time Turing Machines (ITTMs), let $M_i(x)$ denote a computation of an $i$-th ITTM, assuming that the input $x$ is a real (an infinite binary sequence). Then the ...
12
votes
1answer
633 views

Descriptive set theory for computer scientists?

It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the ...
6
votes
0answers
253 views

“Relative plausibility” of some infinitary theories

We work in $\mathsf{ZFC+V=L}$. Define a plausible theory to be a theory $T\subseteq\mathcal{L}_{\omega_1,\omega}$ in an $\omega_1$-finite language which is $\omega_1$-c.e. and $\omega_1$-finitely ...
2
votes
0answers
92 views

Decidable equality for computable functions $\mathbb{N}\to\mathbb{N}$

Suppose we have two computable functions $f, g:\mathbb{N}\to\mathbb{N}$. When is $f=g$ algorithmically decidable? For example it is decidable if $f$ and $g$ are polynomials of a priori known degree.
3
votes
0answers
95 views

Variation in decidability of diophantine equations with field extension

Let $O_k$ be the ring of integers in a subfield $k$ of $\overline{\mathbb{Q}}$. Let's call an equation $p(x_1, \dots, x_n) = 0$ where $p$ is a polynomial in $n$-variables $x_1, \dots, x_n$ with ...
3
votes
1answer
54 views

Ordinal numbers reachable by primitive recursive ordinal functions in omega

$ \def \PRo {{\mathcal { PR } _ \omega}} $ The class of primitive recursive ordinal functions in the constant omega function (henceforth denoted by $ \PRo $) are defined by Jensen and Karp (1971) as ...
2
votes
1answer
82 views

Busy beaver sequence for a simple tag-like system

This question arose in the context of tag-like systems, specifically Bitwise Cyclic Tag (BCT). Consider the following discrete dynamical system: Let $\mathbb{B} = \{\mathtt{0}, \mathtt{1}\}$. Let our ...
1
vote
2answers
587 views

Is there an analogue of the Lost Melody Theorem in ordinary recursion theory and if not, why not?

In their arXiv preprint, "Infinite Time Turing Machines" (arXiv:math/9808093v1 [math.LO] 21 Aug 1998) Hamkins and Lewis state the Lost Melody Theorem for ITTM's as follows: Lost Melody ...
1
vote
0answers
96 views

Why doesn't $\mathsf{B}\Sigma_2$ hold in $\mathsf{RCA}_0$?

For a formula $\varphi(i,u)$ of arithmetic, the bounding principle for $\varphi$ is the statement $$\forall m \, \Big( \big( \forall i<m\ \exists u\ \varphi(i,u) \big) \to \big( \exists v\ \forall ...
3
votes
0answers
121 views

Is a function growing faster than any computable function necessarily independent of ZFC?

Let $\mathrm{BB}:\mathbb{N}\to\mathbb{N}$ be the Busy beaver function. Then we have the following. Let $T$ be a computable and arithmetically sound axiomatic theory. Then there exists a constant $n_T$...
7
votes
1answer
179 views

Independence of $\Pi^1_1$-induction from ATR$_0$

Is it known that $\Pi^1_1$-induction is independent of ATR$_0$? Simpson's book shows this for $\Pi^1_1$ transfinite induction ($\Pi^1_1$-TI), but I'm only interested in inducting on $\omega$. I can ...
0
votes
0answers
52 views

Bijectively parametrize non-negative integers by binary sequences

Given $n\in \mathbb{Z}_{\geq 0}$ denote by $B_n$ the set of binary sequences of length $n$. Denote $B=\bigcup_{n\geq 0} B_n$. Let $P, Q:\mathbb{Z}_{\geq 0}\to\mathbb{Z}_{\geq 0}$ be two computable ...
4
votes
0answers
183 views

Are there any 1-decidable algebraic extensions of $\mathbb{Q}$ which are not decidable?

A model $M$ is decidable if the set of all first-order formulas which are true in $M$ is a recursive set. And a model is $1$-decidable if the set of all existential formulas which are true in $M$ is ...
10
votes
1answer
291 views

What is the Turing degree of the monadic theory of the real line?

The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...
2
votes
0answers
69 views

Is this variant of bitwise cyclic tag Turing-complete? [closed]

Cross-posted from Theoretical Computer Science. CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply ...
5
votes
0answers
136 views

What is known about these “explicitly represented” spaces?

Apologies if this is too low-level. A related question that I asked on the Math Stack Exchange got no answers after a year, so I thought it might be better to ask this one here. The standard approach ...
4
votes
1answer
311 views

Uniform incomparable consistency strengths

For every true arithmetical statement $T$, there are $T$-incomparable $Π^0_1$ statements, but can we find them uniformly in $\text{Theory}(T)$? Specifically, are there computable $A$ and $B$ such that ...
2
votes
0answers
70 views

Good notation for finite partial functions from $\omega$ to 2

I'm working in computability theory and need to use partial functions with finite domain from $\omega$ to 2 as approximations in my current paper. Normally this is simply done using $2^{< \omega}$ ...
0
votes
1answer
153 views

Algorithmically decide if an algorithm has optimal time complexity [closed]

Is there an algorithm with the following input and output? INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs. OUTPUT: "YES"...
5
votes
1answer
168 views

Formula that requires a higher complexity to be proved

Sorry if this question is naive, I am not very well versed in recursion theory. Does it exist a formula $\phi$ such that: $\phi$ is provable in Peano arithmetic $\phi \in \Sigma^0_n$ or $\phi \in \Pi^...
3
votes
0answers
180 views

How to solve special Diophantine equation systems (which one can solve by hand) with the computer?

I have a quadratic Diophantine equation system which is possibly not homogeneous and has some mixed and some linear terms. But I know that there are only finitely many solutions over the integers. One ...
2
votes
1answer
190 views

Uncomputability of a function based on the Busy Beaver function

Let $\log _b^ac$ denote an iterated base-$b$ logarithm function. For example, $$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$ Pick an arbitrary model M of Turing ...
7
votes
1answer
288 views

How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?

There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
-1
votes
1answer
59 views

Big-Oh bound of a recursive function with two variables [closed]

My goal is to obtain the Big-Oh bound of the following recursive function with two variables: $$T(n,m) = T(n, m-1) + T(n-1,m)+1$$ As initial conditions, $T(0,m)=1$ and $T(n, 0)=1$ for $m \geq 0$ and $...
2
votes
1answer
59 views

Arithmetic non-trivial 2-l.u.b

Remember a degree $\mathbb{d}$ is the $n$-lub of $\mathbb{c}_j$ in the Turing degrees if it is the least element (not merely a minimal element) set of $\mathbb{c}^{(n)}$ such that $\mathbb{c}$ ...
9
votes
0answers
255 views

What logic characterizes relative intrinsic complexity in set recursion?

Short version: Is there an analogue of the Ash-Knight-Manasse-Slaman/Chisholm theorem for $E$-recursion? Long version: I'm interested in "$E$-recursive structure theory," but it's not ...
0
votes
0answers
145 views

Proof that $\omega_1^{CK}$ is admissible

An ordinal $\alpha$ is admissible if $L_\alpha\vDash KP$ (Kripke–Platek set theory). $\omega_1^{CK}$ is the least non-recursive ordinal; the set of all recursive ordinals. It is known that $\omega_1^{...
8
votes
1answer
342 views

Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?

The goal of this question is to fill in the gap in this old answer of mine. For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
1
vote
1answer
50 views

Computable in $\omega$-REA degree but not double jump of finitely many columns

Suppose that $A$ is an $\omega$-REA set (so $A^{[n]}$ is r.e. in the prior columns). It is a well-known result that if each column of $A$ is computable then $A \leq_T \emptyset^2$ ($\emptyset^2$ can ...
10
votes
1answer
605 views

What is known in general about the liquid transfer problem?

In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
15
votes
2answers
1k views

Are the vertical sections of the Ackermann function primitive recursive?

The Ackermann function $A(m,n)$ is a binary function on the natural numbers defined by a certain double recursion, famous for exhibiting extremely fast-growing behavior. One finds various slightly ...
4
votes
2answers
357 views

Infinite descending chain of Turing jumps with equality

How can one demonstrate there is no sequence $X_i$ of sets such that $X_{i+1}' = X_i$ (this is really equality as sets though Turing equivalence would be interesting too). I know it fails if I relax ...
1
vote
1answer
41 views

Is a cohesive set always an almost subset of a co-simple set?

A set $A\subseteq\omega$ is called a cohesive set if $C$ is finite for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap(\omega\setminus W_e)$ is finite. And a set $A\...
5
votes
2answers
248 views

Checking for finite fibers in hash functions

Let $\{0,1\}^{<\omega}$ denote the collection of finite binary sequences. By a hash function we mean a computable map $$h: \{0,1\}^{<\omega} \to \{0,1\}^n$$ for some fixed $n\in\omega$. Define $\...
4
votes
1answer
161 views

Is there a “listable” structure of computable dimension $\omega$?

Say that a (countable, computable-language) structure $\mathfrak{A}$ has computable dimension $\omega$ iff there are infinitely many computable copies of $\mathfrak{A}$ up to computable isomorphism. ...
3
votes
1answer
88 views

Does “productive = dimension $\omega$” for computable structures?

In analogy with the terminology for sets, say that a (countable, computable language) structure $\mathfrak{A}$ is productive if there is a computable way to properly expand any computable list of ...
-1
votes
1answer
206 views

ITTM busy beaver function VS Rayo's function

It is known that both functions surpass the Busy Beaver function and $\Xi(n)$, but how do they compare with each other? It seems that people thought I was confused with the definedness of Rayo's ...
2
votes
1answer
89 views

Generality of construction for $\omega$-REA arithmetic degrees

So a common method used to construct non-zero $\omega$-REA arithmetic degrees with various properties is to build an $\omega$-REA operator $J$ satisfying the constraints that (for all $X$) $$\tag{1} J(...
3
votes
1answer
253 views

What is the strength of the second-order statement 'an uncountable closed set in $\mathbb{R}$ has a limit point'?

Perhaps surprisingly, we work in the language of second-order arithmetic. I was wondering if the strength of the following statement LP was known: An uncountable closed set in $\mathbb{R}$ has a ...
5
votes
3answers
343 views

Is there a quantum analog of Kolmogorov Complexity?

Kolmogorov Complexity (interpreted in terms of shortest program computing a string) and Shannon Entropy are quite similar. Since there is a quantum entropy is it reasonable to ask if there is quantum ...
5
votes
1answer
189 views

From Vitali to Heine-Borel in reverse mathematics

The Vitali and Heine-Borel covering theorems are house-hold names of analysis, and rightly well-studied in reverse mathematics. As shown in Simpson's excellent monograph [1], for countable coverings ...

1
2 3 4 5
16