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
10 votes
2 answers
908 views

What Turing-Complete models of computation carry a notion of time complexity that "agrees" with that of Turing Machines?

Certain models of computation are technically Turing-Complete, but cannot feasibly simulate a Turing Machine within the usual time constraints we hope for. One example of this is Godel's recursive ...
GMB's user avatar
  • 1,379
10 votes
1 answer
593 views

What Turing degree is this function?

Over at http://www.scottaaronson.com/blog/?p=2725#comment-1089004 we had a discussion of intermediate Turing degrees. The following function came up: Take Chaitin’s constant, and rearrange its binary ...
ike's user avatar
  • 203
10 votes
1 answer
561 views

Can Tarski decide constructibility in elementary geometry?

Can the decision routine for Tarski's Elementary geometry be extended to decide when an existence claim in that theory can be instantiated by a compass and straightedge construction? The answer does ...
Colin McLarty's user avatar
10 votes
1 answer
267 views

Complexity of the set of models of TA

Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
Dino Rossegger's user avatar
10 votes
2 answers
1k views

What is the precise notion of "enough arithmetic" in Godel's first Incompleteness theorem?

I'm trying to reconstruct the proof of Godel's first theorem (Rosser's strong version) from the uncomputability of the Halting function. If we just started with the language $\mathcal{L}=\{0, S, +, \...
JAN's user avatar
  • 169
10 votes
2 answers
565 views

Transfinite algorithms

The Ford-Fulkerson algorithm is a classic algorithm that computes the maximum flow in a network. It is well-known that if irrational arc capacities are allowed, the algorithm does not necessarily ...
Tony Huynh's user avatar
  • 31.5k
10 votes
1 answer
362 views

Complexity of induction formulas in proof theoretic ordinals

According to The Art of Ordinal Analysis, the proof theoretic ordinal of a theory $T$ is the least ordinal $\alpha$ such that: $${\bf ERA}+TI(\alpha,ECP)\vdash Con(T)$$ In above definition, $ECP$ ...
Erfan Khaniki's user avatar
10 votes
1 answer
400 views

The least admissible above a dominating real

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
Noah Schweber's user avatar
10 votes
0 answers
230 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 ...
Sam Eisenstat's user avatar
10 votes
0 answers
443 views

(A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
Noah Schweber's user avatar
10 votes
0 answers
207 views

Can we find minimal-diameter metrics without computability?

A beautiful argument by Nabutovsky and Weinberger (see http://math.uchicago.edu/~shmuel/fractal.ps) shows that, if $M$ is any smooth compact manifold of dimension $\ge 5$, then the diameter functional ...
Noah Schweber's user avatar
9 votes
5 answers
2k views

Are there natural, small, and total recursive functions that are not primitive recursive?

In a sense the Ackermann function is not primitive recursive (PR) because it grows too fast. Are there total recursive, not PR, small functions? Using a diagonal argument, we may define a total ...
Armando Matos's user avatar
9 votes
3 answers
2k views

What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
Wolphram jonny's user avatar
9 votes
3 answers
808 views

Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
user avatar
9 votes
2 answers
1k views

Recursive presentations

A recursive presentation of a group is a one in which there is a finite number of generators and the set of relations is recursively enumerable. I found the following quote in Lyndon-Schupp, chapter ...
Lukasz Grabowski's user avatar
9 votes
4 answers
922 views

Are there two computable binary trees such that each has a branch not computing any branch through the other?

It is a well-known elementary classical result in computability theory that there are computable infinite binary trees $T\subset 2^{<\omega}$ having no computable infinite branch. (One can build ...
Joel David Hamkins's user avatar
9 votes
2 answers
2k views

What is the probability a random Turing machine is isomorphic to a DFA?

This is a sort of Chaitin/Omega constant type question, and so I do not expect this probability to be computable to arbitrary precision. However, it is also a very practical thing to know from the ...
Mikola's user avatar
  • 2,342
9 votes
2 answers
2k views

Busy Beaver - Proof for BB(2) = 4

Hi, I need to prove the above claim. I can show that $BB(2)\ge 4$ by building a turing machine, but how can i show that $BB(2) \le 4$? Searched a lot over the web, and saw that Rado proved it in ...
Alan's user avatar
  • 99
9 votes
2 answers
916 views

What theories are larger than the real closed field but still decidable?

It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
Sidharth Ghoshal's user avatar
9 votes
1 answer
793 views

Are there 'finitistic' nonrecursive functions (assuming Church's Thesis is false)?

[Note: In what follows, I will be using the same type of argument Laszlo Kalmar did in his paper "An Argument Against the Plausibility of Church's Thesis" found in Constructivity in Mathematics, (...
Thomas Benjamin's user avatar
9 votes
2 answers
909 views

Non null Turing antichain

This interesting question resulted from a query of Mushfeq: In ZFC, can we find a non null set of pairwise Turing incomparable reals?
Ashutosh's user avatar
  • 9,771
9 votes
1 answer
684 views

Computable models of the ordinal numbers

It's known, for example in the answer to this question: Is there a computable model of ZFC? that ZFC has no computable model. My questions is: is there a model of ZFC for which the order relation on ...
Raul Gomez's user avatar
9 votes
1 answer
663 views

Can you decide whether the commutator subgroup of a f.p. group is f.g?

Is the following algorithmic problem known to be decidable/undecidable? Input: a finite group presentation $P$. Decide: is the commutator subgroup of the group presented by $P$ finitely generated?
suitangi's user avatar
  • 333
9 votes
2 answers
814 views

Decidability of diophantine equation in a theory

Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows: Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether $...
srs's user avatar
  • 193
9 votes
1 answer
601 views

Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
Dave Albert's user avatar
9 votes
2 answers
1k views

What are the limits of non-halting?

It's easy enough to build Turing Machines that don't halt. But how complex can we make these? For example, suppose a machine has access to its state transition table and can write to it like a C ...
Stanislav's user avatar
  • 101
9 votes
1 answer
705 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 ...
Noah Schweber's user avatar
9 votes
2 answers
1k 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 ...
ಠ_ಠ's user avatar
  • 5,933
9 votes
1 answer
578 views

Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
Joel David Hamkins's user avatar
9 votes
1 answer
272 views

A homeomorphism with a prescribed action on the fundamental group - decidable or not?

I am curious if the following topological problem is decidable. Let $M,N$ be two closed manifolds. Given a group isomorphism $p: \pi_1(M)\to \pi_1(N)$, is there a homeomorphism $\phi: M\to N$ such ...
Alex Gavrilov's user avatar
9 votes
1 answer
530 views

Dodgy Turing degrees

This question was originally asked and bountied at MSE, but received no answer there, so I'm asking it again here. Below, I'm specifically interested in weak truth table (wtt) reducibility, but other ...
Noah Schweber's user avatar
9 votes
1 answer
839 views

Uncountable time Turing machines

When writing with a friend of mine today we came up with idea of extending ITTM concept of Hamkins and Kidder. First of all, I am familiar with one of Hamkins and Lewis results saying that every ...
Wojowu's user avatar
  • 27.4k
9 votes
1 answer
509 views

Cohesive sets with degree below some non-high 1-generic degrees?

Terminology: Cohesive sets: $A\subset \omega$, for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap(\omega\setminus W_e)$ is finite. Non-high degrees: Degree $a$ such ...
Jing Zhang's user avatar
  • 3,138
9 votes
1 answer
337 views

Minimal cover v.s random reals

The following set theoretical question is inspired by a question from recursion theory: Question: Is there an $L$-random real $r$ which is a minimal cover over another real $x$? Where a minimal ...
喻 良's user avatar
  • 4,191
9 votes
2 answers
555 views

Where should I learn about Kolmogorov complexity of overlapping substrings?

I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(...
Linda Brown Westrick's user avatar
9 votes
1 answer
311 views

Ensuring nonempty lightface Borel sets have elements via theories of second-order arithmetic

This question is an outgrowth of this MathSE question: https://math.stackexchange.com/questions/276068/members-of-lightface-borel-sets. A Borel set $X\subseteq 2^\omega$ is a member of the smallest ...
Noah Schweber's user avatar
9 votes
1 answer
408 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 ...
Noah Schweber's user avatar
9 votes
3 answers
613 views

Finite realization of irrational transfer functions

In the field of digital signal processing, linear time-invariant systems play a distinguished role. These are the systems for which there exists an impulse response, a function $h:\mathbb{Z}\to\...
Noah Stein's user avatar
  • 8,403
9 votes
1 answer
261 views

Cohesive set with degree below non-high Martin-Löf random reals

A set A is cohesive if $A\subseteq ^* W_e$ or $A\subseteq^* \bar{W_e}$ for each $e\in \omega$ (standard enumeration of r.e. sets). By Jockusch and Stephan's 1993 paper 'A cohesive set which is not ...
Jing Zhang's user avatar
  • 3,138
9 votes
1 answer
481 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 ...
Max CYLin's user avatar
  • 151
9 votes
1 answer
419 views

First order axioms for primitive recursion in Takeuti's theory of ordinal numbers

In this article, Takeuti has introduced a theory of ordinal numbers, which in his own words, is intended to be a first order theory: The theory of ordinal numbers we are to develop is based on the ...
Mohsen Shahriari's user avatar
9 votes
0 answers
283 views

Coding third-order objects via second-order ones

As is well-known, the language of second-order arithmetic only has variables for natural numbers and sets of natural numbers. Higher-order objects, like functions on $\mathbb{R}$, have to be ...
Sam Sanders's user avatar
  • 3,901
9 votes
0 answers
271 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 ...
Noah Schweber's user avatar
9 votes
0 answers
336 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)$ ...
Kaban-5's user avatar
  • 543
9 votes
0 answers
295 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 ...
Noah Schweber's user avatar
9 votes
0 answers
523 views

"Hard" separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
Noah Schweber's user avatar
8 votes
4 answers
3k views

The Halting Problem and Church's Thesis

In the opening chapters of Hartley Rogers, Jr.'s book Theory of Recursive Functions and Effective Computability, the proofs of the unsolvability of the halting problem and related unsolvability ...
Frode Alfson Bjørdal's user avatar
8 votes
3 answers
1k views

Is there a "primitive-recursively enumerable" set whose complement is not such?

Call a subset of $\mathbb{N}$ primitive-recursively enumerable (p-r.e.) if it is empty or an image of a primitive recursive function. I feel like a lot must be known about the poset of such sets ...
Andrej Bauer's user avatar
  • 47.7k
8 votes
2 answers
553 views

Turing degrees of sets separating two computably inseparable sets (theorems and antitheorems)

Let $A\subseteq\mathbb{N}$ be the set of Gödel codes of theorems of Peano arithmetic, and $B\subseteq\mathbb{N}$ be the set of codes of antitheorems (i.e, refutable statements, statements whose ...
Gro-Tsen's user avatar
  • 29.9k
8 votes
2 answers
868 views

Did Bishop, Heyting or Brouwer take partial functions seriously?

The partial μ-recursive functions which may or may not be provably total seem to have some direct relation to the initial motivations for intuitionistic mathematics. (Following Kronecker, one ...
Thomas Klimpel's user avatar

1
3 4
5
6 7
20