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

**0**

votes

**0**answers

59 views

### Enumerating Bring radicals

This question here seems to ask only about finite collections of Bring radicals, what about infinite collections, is there a Turing machine, which would list all the necessary radicals one-by-one?

**10**

votes

**2**answers

614 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

345 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

46 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

129 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

51 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

126 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

198 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

120 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

249 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

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

**88**

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

**1**

vote

**0**answers

58 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) ...

**1**

vote

**0**answers

66 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

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

**21**

votes

**2**answers

635 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

96 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

811 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

152 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

53 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

80 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

186 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

320 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

147 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

117 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

125 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

535 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

118 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

403 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

138 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

388 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

363 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

133 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

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

**17**

votes

**2**answers

742 views

### For a computable binary tree, is having no computable branches the same as having no probabilistic algorithm for producing branches?

It is a classical result of computability theory that there is a
computable infinite binary tree $T\subset 2^{<\omega}$ with no
computable infinite branch.
One way to construct such a tree is to ...

**9**

votes

**0**answers

240 views

### Moschovakis' discovery of E-recursion

E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded ...

**3**

votes

**0**answers

83 views

### Reducibilities: Muchnik versus Medvedev-mod-parameters

By "structure," I mean "countable first-order structure in a computable language." And I'm comfortable with whatever set-theoretic hypotheses make things most interesting, should such things be ...

**12**

votes

**2**answers

2k views

### Proof there is no algorithm to compute the intersection of a line and sinusoidal wave?

There is obviously a set of situations where one lack an algorithm to compute the exact solution of an equation via symbolic manipulation only, for example ...

**4**

votes

**2**answers

121 views

### Different notions of computable binary sequence

The standard definition of computability, for a sequence $s\in\{0,1\}^\omega$, is that there is a Turing machine outputting $s[i]$ on input $i$.
I'm looking for strengthenings of this notion; for ...

**2**

votes

**1**answer

151 views

### Is there an oracle that can compute something iff it is computable in every countable model that is equivalent to $(V, \in)$?

Let us work in Kelly-morse set theory, so we can talk about $V$. For some model $M=(\mathbb N, \in_M)$ that is elementary equivalent $(V, \in)$, we can have an oracle that corresponds to $(\mathbb N, \...

**10**

votes

**0**answers

135 views

### Can we internalize topological fixed point theorems in an effective topos?

Reflective oracles are a kind of Turing oracle that give stochastic answers about the outputs of Turing machines. This works in a self-referential way, where they can answer queries about Turing ...

**2**

votes

**2**answers

222 views

### Connection between countable ordinals and Turing degrees

$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...

**0**

votes

**0**answers

84 views

### Name and theory of multi-valued functions $F:\mathbb{N}^k \rightarrow \mathbb{N}^l$

In computability theory there are considered mostly single-valued functions $f:\mathbb{N}^k \rightarrow \mathbb{N}$. (Let $\mathbb{N}$ be a placeholder for $\mathbb{N}$ or any initial segment $[0,n]$ ...