# 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 ...

**1**

vote

**0**answers

64 views

### A strong plus-one hypothesis

To make this more easily readable, I'll start with the question and then give the explanation/motivation.
Question. Is the following principle (or its weakening, with "for every real $r$" replaced ...

**0**

votes

**1**answer

42 views

### Meaning of “Herbrand-Goedel recursive” in Kleene's “On Notation for Ordinal Numbers”

In Kleene's "On Notation for Ordinal Numbers", Journal of Symbolic Logic, Volume 2, Number 4, December 1938, he says that a function of natural numbers is taken to be effective if it is Herbrand-...

**2**

votes

**1**answer

169 views

### Meta-incomputability

Is there a set $B$ about which it provably cannot be decided whether it is computable in $\mathsf{ZFC}$?

**1**

vote

**1**answer

97 views

### Set of integer matrices $A$ such that $(A^k)_{k\in\mathbb{N}}$ is eventually periodic

This is a more elegant version of the original version which can be found below; it is based on a suggestion by Peter Mueller.
Let $\mathbb{N}$ denote the set of positive integers and for $n\in\...

**15**

votes

**2**answers

399 views

### Is Post's tag system solved?

Has the 3-tag system investigated by Emil Post $(0\to00, 1\to1101)$ been solved? Is there a decision algorithm to determine which starting strings terminate, which end up in a cycle, and which (if any)...

**4**

votes

**0**answers

104 views

### Subgroup membership problem for Noetherian groups

I am interested in the status of the subgroup membership problem (MP) for finitely presented Noetherian groups. That is, given a finite presentation $\langle X,R\rangle$ for a Noetherian group,
\begin{...

**2**

votes

**0**answers

51 views

### What are the moments of Kolmogorov Complexity for a Random Variable?

Given a random variable $X$ distributed under some computable distribution $P$ we have,
$$0 \le E[K(X)] - H(P) \le K(P)$$
Where $H(P)$ is the entropy of $P$. I tried using Hoeffding concentration ...

**4**

votes

**0**answers

102 views

### The set of homogeneous solutions of a clopen contains an hyperarithmetical set

In the context of Galvin-Prikry generalization of Ramsey's theorem, I read in a couple of papers ([1],[2]) that Solovay [3] proved that if $P$ is a clopen of $[\mathbb{N}]^{\mathbb{N}}$ then the set ...

**5**

votes

**0**answers

101 views

### Natural examples of recursive pseudowellorderings

Question: What are some natural examples of recursive pseudowellorderings?
By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...

**5**

votes

**1**answer

234 views

### Progress towards a computational interpretation of the univalence axiom?

I will preface this by saying that I am not an expert on type theory. I am just a curious outsider slowly making my way through the HoTT book when I (rarely) have some spare time.
I am just curious ...

**11**

votes

**2**answers

657 views

### Is being close to a Halting set computable?

Let $\Phi$ be a universal Turing machine and let $S$ be the set on which it halts. I’m curious about if its decidable to check if a number is close to $S$. There are two notions of distance that come ...

**16**

votes

**1**answer

364 views

### What non-standard model of arithmetic does Hofstadter reference in GEB?

Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...

**2**

votes

**1**answer

48 views

### Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra

Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...

**11**

votes

**0**answers

145 views

### Is homeomorphism of simplicial complexes semidecidable?

Conventions: $\cong$ is homeomorphism of topological spaces and isomorphism of groups, $\equiv_G$ is the equality of two words over the generators of the group $G$. Simplicial complexes are finite.
...

**0**

votes

**1**answer

56 views

### Probabilistic generalization of trial-and-error predicates

The notion of a limiting recursive set (Gold 1965, J. Symb. Log. 30: 28–48) or trial and error predicate (Putnam 1965, J. Symb. Log. 30: 49–57) is defined as follows. A guessing function is a total ...

**18**

votes

**2**answers

1k views

### Is there a known Turing machine which halts if and only if the Collatz conjecture has a counterexample?

Some of the simplest and most interesting unproved conjectures in mathematics are Goldbach's conjecture, the Riemann hypothesis, and the Collatz conjecture.
Goldbach's conjecture asserts that every ...

**3**

votes

**1**answer

128 views

### Strongly reducible but not effectively interpretable

A countable structure A is strongly reducible to a structure B if there is a uniform turing functional which, given a copy of the atomic diagram of B, computes a copy of the atomic diagram of A.
A is ...

**7**

votes

**0**answers

212 views

### Co-cones in the Turing degrees

Let the cocone of a Turing degree ${\bf d}$ be the set $cc({\bf d}):\{{\bf c}: {\bf c}\not\ge_T {\bf d}\}$. I'm curious what's known about the various partial orders (isomorphic to ones) of the form $...

**2**

votes

**1**answer

121 views

### Is this cycling problem computable?

We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they ...

**30**

votes

**2**answers

1k views

### How (non-)computable is set theory?

Here is a naive outsiders perspective on set theory: A typical set-theoretical result involves constructing new models of set theory from given ones (typically with different theories for the original ...

**8**

votes

**0**answers

257 views

### Is Videla's solution of Hilbert's tenth problem for rational functions over field of characteristic 2 wrong?

The paper in question.
Quick introduction to the problem: suppose that $F$ is a finite field of characteristic 2
(for purposes of this post $F = \mathbb{F}_2$ will suffice) and let $F[t]$ and $F(t)$ ...

**6**

votes

**1**answer

154 views

### Correspondence between proof-theoretic ordinals and fast growing functions?

For theories with well known proof-theoretic-ordinals, (what) is there a correspondence between their proof-theoretic-ordinal and (ordinal indexed families of?) fast growing functions provable total ...

**93**

votes

**9**answers

11k views

### On Mathematical Arguments Against Quantum Computing

Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...

**2**

votes

**0**answers

59 views

### What is the relation of total functions in second order arithmetic and fast growing hierarchies?

Answer to this questions shows that fast growing hierarchies can grow arbitrarily fast for some definition of 'arbitrary'.
Can second order arithmetic define all these functions (for any ordinal) ...

**2**

votes

**0**answers

71 views

### Is the quantifier-free fragment of Robinson arithmetic essentially undecidable?

It is well known that Robinson arithmetic (Q) is undecidable, and in fact essentially undecidable. Matiyasevich's theorem implies that the quantifier-free fragment of Q is also undecidable. However, I'...

**5**

votes

**1**answer

325 views

### Can an uncountable model of Peano Arithmetic be recursive?

Can an uncountable model of Peano Arithmetic be recursive?
What does it mean for an uncountable model to be recursive? Well, we represent the elements of the model using real numbers instead of ...

**22**

votes

**2**answers

695 views

### Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...

**6**

votes

**1**answer

100 views

### Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C join X computes B

Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can ...

**25**

votes

**2**answers

839 views

### Is the cohomology ring of a finite group computable?

Is there an algorithm which halts on all inputs that takes as input a finite group ($p$-group if you like) and outputs a finite presentation of the cohomology ring (with trivial coefficients $\mathbb{...

**1**

vote

**0**answers

154 views

### Lowest Turing degree that allows a Turing machine to tell whether $\operatorname{Con}(PA)$?

Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...

**1**

vote

**1**answer

94 views

### function application [closed]

Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement.
For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following ...

**2**

votes

**1**answer

55 views

### Name for “partially complete” invariants in classification problems?

For any equivalence $\sim$ on some collection of objects $C$ consider the problem of trying to determine if two arbitrary objects $x$ and $y$ in $C$ are equivalent i.e. if $x\sim y$ now by definition ...

**2**

votes

**0**answers

82 views

### what is the relationship between the complexity of a function and the complexity of it's graph set?

Given $f: \omega \rightarrow \omega$ , what is the relationship between the following two notions:
(i) the computational complexity of f (in the standard sense, say with naturals represented in ...

**3**

votes

**2**answers

187 views

### Can all lengths of shortest non-halting inputs of all Turing machines be limited by the Busy Beaver applied to the corresponding numbers of states?

Let $E_1$ denote the infinite enumerated collection of two-symbol (0 as blank symbol and 1 as non-blank symbol) one-tape (...

**8**

votes

**1**answer

323 views

### Axiomatizable $\exists \forall$ theory

I have been thinking the following problem proposed by my friends for a long time.
Let $\mathcal{L}$ be the first-order language of theory of rings and let $K$ be the class of algebraic number ...

**4**

votes

**1**answer

97 views

### Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants

In their paper "Theories with recursive models" [1] Lerman and Schmerl used a version of Kruskal's tree theorem about finite n-augmented trees.
An n-augmented tree is a tree T together with $n$ unary ...

**6**

votes

**0**answers

85 views

### Deciding when certain elements of $L[[x]]$, coming from recursions, are algebraic over $L(x)$

Let $L$ be a finite field of characteristic $2$. Suppose that for some $k > 0$ we are given elements $A(0),\, A(1), \dots, \, A(k-1)$ and $c(0),\, c(1), \dots,\, c(k-1)$ of $L[t]$. Define $A(n)$ ...

**4**

votes

**0**answers

150 views

### Tileability and computabilty

Let $n>2$ be an integer. We consider $n$ pairs $(x_1,y_1),\dotsc,(x_n,y_n)$ in $\mathbb{N}^2$, and the polygon defined by drawing a straight line from $(x_k, y_k)$ to $(x_{k+1},y_{k+1})$ and from $(...

**8**

votes

**0**answers

118 views

### Is every total computable function definable by a strongly total lambda term?

Every computable (total) function $f : \mathbb{N} \to \mathbb{N}$ is definable in untyped pure lambda calculus in the sense that there is a term $F$ such that, for every Church's numeral $c_n = \...

**8**

votes

**1**answer

163 views

### Is every total computable function definable by a normalizing lambda term?

$\newcommand{\nat}{\mathbb{N}}$
$\newcommand{\then}{\ \Longrightarrow\ }$
A partial function $f : \mathbb{N} \to \mathbb{N}$ is said to be $\lambda$-definable if there is a term $F \in \Lambda$ such ...

**1**

vote

**0**answers

55 views

### Predicting even bits with the universal prior

If the universal prior is fed a sequence where all even bits are 0 and all odd bits are drawn from some computable distribution, it will eventually become near-certain that the next 1000 even bits are ...

**2**

votes

**0**answers

129 views

### minimum size of undecidable quadratic diophantine problems

According to Matiyasevich, the existence of integer solutions of systems of polynomial equations with integer coefficients is undecidable. By introducing additional variables substituting factors of ...

**20**

votes

**3**answers

554 views

### Defining computable functions categorically

Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...

**0**

votes

**0**answers

119 views

### Elementary Question Regarding Classification of some Subsets of $\mathbb{N}$

The question is regarding a few easily described subsets of $\mathbb{N}$. I have difficulty identifying which classification they fall into. These certainly feel like questions that would be present ...

**6**

votes

**2**answers

409 views

### Reasoning Using Countable Subsets of Real Numbers

The purpose of my question is trying to understand whether, in some cases, we can achieve greater certainty of reasoning (say when dealing with statements about natural numbers, integers or rational ...

**2**

votes

**0**answers

140 views

### The elementary theory of finite commutative rings

I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...

**8**

votes

**1**answer

398 views

### Can the Turing degrees be linearly ordered?

Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...

**15**

votes

**1**answer

369 views

### Would an oracle for Rayo's function let you compute a model of $(V, \in)$?

Working in Kelly-morse set theory, let $R$ be an oracle that can compute Rayo's function. Can $R$ compute a countable model $M = (\mathbb N,\in_M)$ that is elementary equivalent to $(V, \in)$?

**1**

vote

**1**answer

138 views

### Is Calculus of Constructions type inhabitance semi-decideable?

I'm wondering if type inhabitance for the calculus of constructions is semi-decideable. I know the following:
System F inhabitance and, correspondingly, second-order unification are semi-decideable
...

**5**

votes

**1**answer

133 views

### A “dense” extension of the set of primitive recursive functions

Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...