**6**

votes

**2**answers

141 views

### a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known.
I need a variant. (For those in the know, I need a c-bar which is ...

**5**

votes

**1**answer

121 views

### “Partial-computably isomorphic” sets

For $A,B \subseteq \mathbb{N}$, define $A\sim B$ when there exist partial computable functions $f,g\colon \mathbb{N}\rightharpoonup \mathbb{N}$ such that $f$ is defined at least on all of $A$ and $g$ ...

**4**

votes

**0**answers

159 views

### Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...

**2**

votes

**2**answers

509 views

### Can we compute every definable number with knowledge of the halting problem?

Suppose we knew the answer to the halting problem, and the halting problem for this new system with the old halting problem solved. And so on. Would this allow us to compute every definable number?

**16**

votes

**1**answer

1k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**0**

votes

**0**answers

93 views

### Distribution of definable integers

Consider the distribution of all formulas of length less then n which define an integer in PA.
So for instance f(7,n)=number of formulas of length less then n which output 7.
Or the number of steps ...

**3**

votes

**1**answer

218 views

### Can we use this symbol? [closed]

We consider the ring $\mathbb{C}[e^{\lambda x} \mid \lambda \in \mathbb{C}]$ and the language $L=\{+, \cdot , \frac{d}{dx} , 0, 1\}$.
The ring consists of elements of the form $$\sum_{i=0}^N ...

**16**

votes

**1**answer

1k views

### Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...

**0**

votes

**0**answers

143 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the ...

**2**

votes

**2**answers

256 views

### Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...

**8**

votes

**2**answers

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

**14**

votes

**2**answers

449 views

### Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...

**5**

votes

**0**answers

142 views

### List of finitely presented groups with undecidable word problem

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?
By "representative" I mean "avoiding obvious redundancy", i.e. examples ...

**3**

votes

**2**answers

222 views

### Comparing really big numbers

Is there an intractability theorem that says that in any sufficiently rich system for defining really big numbers, there will be two numbers for which it's very, very, ... very difficult to decide ...

**4**

votes

**2**answers

149 views

### Does the notion of provably total function depend on the chosen representation?

A typical definition of "provably total function in a theory $T$" goes like this (paraphrased from Odifreddi, Classical Recursion Theory II):
A function $f : \mathbb{N}^n \to \mathbb{N}$ is ...

**2**

votes

**1**answer

205 views

### Effectively non-recursiveness of some sets

A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$. A set is effectively non-recursive if it is r.e. and its ...

**5**

votes

**0**answers

230 views

### Rice-like Theorems

Let $\varphi$ be an acceptable programming system. Consider the set $S=\{x\in\mathbb{N}:\varphi_x=\varphi_{x+1}\}$. By using Rogers' Fixed Point Theorem (RFPT) it can be proved that $S$ is a ...

**8**

votes

**0**answers

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

**1**

vote

**0**answers

74 views

### A reference for “Borel Sets and Circuit Complexity”

Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?

**4**

votes

**1**answer

73 views

### What class of probability distributions do probabilistic turing machines induce? [closed]

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?

**17**

votes

**1**answer

429 views

### Are compact topological $n$-manifolds recursively enumerable?

Earlier this year it was asked on MO, "Are there only countably many compact topological manifolds?" Thanks to Cheeger and Kister, the answer is yes. On the other hand, Manolescu recently debunked ...

**13**

votes

**0**answers

135 views

### Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...

**10**

votes

**0**answers

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

**11**

votes

**1**answer

251 views

### Can there be computable non-standard models of PA in a weaker sense?

By Tennenbaum's theorem, in the usual sense of computability for models,
neither addition nor multiplication can be computable in a non-standard model of PA.
Weak version:
Can addition or ...

**12**

votes

**2**answers

380 views

### Woodin on Posner-Robinson for the hyperjump and sharp

The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ ...

**21**

votes

**2**answers

731 views

### Antirandom reals

This is a crossposting of http://math.stackexchange.com/questions/1446602/anti-random-reals, which has not gotten any answers; after thinking about the problem, I've become more convinced that it ...

**4**

votes

**1**answer

97 views

### Is DNC/DNR stronger than “prompt” non-computability?

We propose a (probably not new) definition. Let $\varphi_e$ be an effective enumeration of the partial computable functions.
A total function $f$ is promptly non-computable (PNC) [or promptly ...

**0**

votes

**1**answer

116 views

### Computability of prime difference function

Consider the following function $f: \omega\to \{0,1\}$:
Set $f(n) = 1$ if for all $k\in \omega$ there are prime numbers $p,q > k$ such that $n = p-q$; and set $f(n) = 0$ otherwise.
(Trivially, if ...

**9**

votes

**2**answers

759 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?

**4**

votes

**0**answers

104 views

### Can non-computable real numbers be defined without making use of any notions from computability theory

I am not sure if this type of question is appropriate for "mathoverflow.net", but I will take the chance. Are there any examples of (well-known or interesting) problems in geometry which ask for the ...

**4**

votes

**1**answer

120 views

### Analogy of $\omega$-models in constructive mathematics

I apologize that this question is a bit vague, however that is partially the point.
In subsystems of second order arithmetic, one considers $\omega$-models, these are models of $\mathsf{RCA}_0$ whose ...

**6**

votes

**0**answers

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

**2**

votes

**1**answer

187 views

### Is every computable real primitively recursively computable?

Let N be the set of all positive integers and let P(n),Q(n) be a pair of general recursive mappings of N into itself such that for all pairs h,k of distinct positive integers, the absolute value of ...

**4**

votes

**0**answers

109 views

### Undecidability of the existential theory

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, ...

**1**

vote

**1**answer

72 views

### floating point representation via the perspective of TTE/computable analysis

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...

**4**

votes

**1**answer

74 views

### Is every pair of writable reals one-tape-ITTM-computable?

I've been reading this paper, in which authors prove that not all ITTM-computable functions $\Bbb R\rightarrow\Bbb R$ are 1-tape-computable, but if we put some restriction on the output of the ...

**1**

vote

**2**answers

141 views

### Precise interpretability strength of $\mathcal P_{DF}(\omega)$ and $L_{\omega_1^{CK}}$

I am curious about the relationship between the definable power set of $\omega$ and the $\omega_1^{CK}$th level of the constructible sets $L$.
In short, $\omega_1^{CK}$ is the least nonrecursive ...

**0**

votes

**2**answers

145 views

### Undecidable set of problems [closed]

Is there some set of problems, for which determining if given problem is decidable or not is itself undecidable?

**5**

votes

**2**answers

289 views

### Is every non-empty $\Delta_0$ set provably the range of some primitive recursive function?

Suppose $A(x)$ is a $\Delta_0$ formula defining a non-empty set of natural numbers. It's an easy theorem that there is a primitive recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ such that ...

**-1**

votes

**1**answer

243 views

### Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...

**3**

votes

**0**answers

105 views

### Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...

**1**

vote

**2**answers

307 views

### Recent progress on the busy beaver problem? [closed]

Has there been any progress on the Busy beaver problem in the last few years? It seems like there hasn't been much work done on the problem since 2010. Is there anything amateurs can do to solve the ...

**7**

votes

**0**answers

182 views

### $\alpha$-minimal degrees for singular $\alpha$

An important question in $\alpha$-recursion theory is whether there is a minimal $\alpha$-degree at $\alpha=\aleph_\omega.$
Question 1. Who first introduced the above question, and where can I find ...

**-1**

votes

**1**answer

104 views

### recursively enumerable sets [closed]

A set $S$ said to be recursively enumerable if There is an algorithm that enumerates the members of $S$. That means that its output is simply a list of the members of $S$: $s_1$, $s_2$, $s_3$, ... . ...

**10**

votes

**1**answer

209 views

### Is an explicit $c$ known to lead to a noncomputable Julia set?

Braverman & Yampolsky have shown that there exist noncomputable Julia sets,
i.e., there exist $c \in \mathbb{C}$ such that the Julia set of $f(z) = c + z^2$
is not computable.
"A set is ...

**7**

votes

**2**answers

335 views

### Topological tameness beyond the Gandy-Harrington topology

The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$.
...

**1**

vote

**0**answers

116 views

### Analogue break down between complexity theory and computability theory

Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving ...

**6**

votes

**1**answer

238 views

### Can ITTM recognize a non-measurable set?

Throughout the question ITTM refers to Hamkins' infinite Turing machines, though I will be interested in results related to stronger models.
Recently I was wondering, is it consistent that there is ...

**4**

votes

**1**answer

188 views

### Induction and nonstandard halting times of standard machines

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: ...

**6**

votes

**1**answer

137 views

### Minimal degrees of structures

For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$.
Given a ...