Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
1answer
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
9answers
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
0answers
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
0answers
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
0answers
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
3answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
2answers
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
2answers
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
1answer
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
0answers
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
2answers
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
0answers
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]$ ...