**10**

votes

**1**answer

830 views

### Can an infinite number of mathematicians guess the number in a box with only one error?

In this question the following observation was made:
Consider a sequence of boxes numbered 0, 1, ... each containing one real number. The real number cannot be seen unless the box is opened.
Define ...

**3**

votes

**1**answer

138 views

### Productive sets and indices of constant functions

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. Recall that a set $S$ is productive if there exists a recursive function $p$ such that $(\forall x)(W_x\subseteq S\Rightarrow ...

**2**

votes

**0**answers

131 views

### Equivalence of LOOP (primitive recursive functions) and of SRL (reversible transformations) programs

This is a question about the decidability of program equivalence.
Primitive recursive functions correspond exactly to the functions
that can be implemented on a specific register machine usually
...

**4**

votes

**0**answers

321 views

### About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...

**6**

votes

**2**answers

749 views

### Why is there no product type in simply typed lambda-calculus?

Consider simply typed $\lambda$-calculus that has only the unit type as primitive. We would like to encode the product and the sum types. An encoding of the product type in the untyped ...

**10**

votes

**2**answers

363 views

### Is equivalence of functions built from nested exponentiations a decidable problem?

Let $\mathcal{E}$ be the minimal set of symbolic expressions (without any predefined meaning) such that
The symbol $x$ is in $\mathcal{E}$, and
If expressions $P,Q\in\mathcal{E}$, then the ...

**3**

votes

**3**answers

273 views

### Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA

In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...

**3**

votes

**3**answers

428 views

### Infinite Partitions of the Primes and Sums of Reciprocals (Revised)

I have revised my original post. The questions I asked there were not well-put or even thought through. I don't want to delete, however, since some of the comments may be of interest to other MO ...

**12**

votes

**1**answer

422 views

### Ackermann's function over the reals

Ackermann's function is defined over integers $x$, $y$, $A(x,y)$,
with conditions for when $x{=}0$ or $y{=}0$, and otherwise uses recursive
definitions involving arguments $x{-}1$ and $y{-}1$.
Is ...

**3**

votes

**1**answer

97 views

### Disobedience of some complete r.e. set to some additive cost function

An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the ...

**4**

votes

**1**answer

232 views

### Nondeterministic Turing machines and the recursion theorem

This is almost certainly a silly question, but:
I am currently reading Moschovakis' article "Kleene's amazing second recursion theorem" (http://www.math.ucla.edu/~ynm/papers/1602-002-1.pdf) and there ...

**3**

votes

**2**answers

299 views

### Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...

**1**

vote

**0**answers

85 views

### Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...

**2**

votes

**0**answers

257 views

### Sorting of countabe set [closed]

Let $X$ be a countable ordered set. My question is very simple - Can we sort $X$ in countable number of steps?
When $X$ is finite, the answer is obviously yes. But what is the answer when $X$ is ...

**18**

votes

**4**answers

881 views

### Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...

**9**

votes

**1**answer

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

**2**

votes

**1**answer

201 views

### String transformer : Polynomial time approximation schemes?

A program P takes a string as an input and returns a string of same length as output.
Q Given two strings A and B how fast can a program tell weather string B cannot be obtained by a recursive ...

**7**

votes

**1**answer

169 views

### A well-behaved $A$ that is almost contained in every element of some filter for a countable arithmetically closed family $\mathfrak X$

The question has relevance for constructing Scott sets with certain extra desirable properties.
Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: ...

**8**

votes

**3**answers

373 views

### If an oracle Turing machine halts with every infinite arithmetic oracle, can it fail to halt with some non-arithmetic oracle?

Let $e$ be an index of an oracle Turing machine program and $k$ be some natural number. Let us say that a subset of $\mathbb N$ is arithmetic if it is definable in the model $\langle \mathbb ...

**3**

votes

**1**answer

241 views

### Reverse mathematics, Ramsey theorem and mass problem

If we look at reverse mathematics statements as mass problems, considering the class of solutions of an instance, it is known that Weak König's lemma has a maximal instance in the sense that there is ...

**10**

votes

**2**answers

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

**1**

vote

**3**answers

183 views

### unbounded complexity

If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting ...

**9**

votes

**2**answers

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

**3**

votes

**1**answer

188 views

### Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...

**8**

votes

**1**answer

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

**9**

votes

**1**answer

308 views

### Concerning Silver's result

Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists.
I wonder whether various weaker or stronger versions of Silver's result ...

**28**

votes

**3**answers

2k views

### Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?

Is there an algorithm which, given a polynomial $f \in \mathbb{Q}[x_1, \dots, x_n]$,
decides whether the mapping $f: \mathbb{Q}^n \rightarrow \mathbb{Q}$ is surjective,
respectively, injective? --
And ...

**21**

votes

**1**answer

565 views

### Busy Beaver modulo 2

There is well-known Rado's "Busy Beaver" sequence — the maximal number of marks which a halting Turing machine with n states, 2 symbols (blank, mark) can produce onto an initially blank two-way ...

**6**

votes

**1**answer

409 views

### Where does the deterministic simulation of non-deterministic ω-Turing machines fail?

An $\omega$-Turing machine is just a usual Turing machine $T=(Q,\Sigma,\Gamma,\delta,q_0,F)$ where $Q$ is the finite set of states, $\Sigma$ is the input alphabet, $\Gamma\supset\Sigma$ is the tape ...

**2**

votes

**1**answer

154 views

### $\mu$-recursive definitions for the complexity classes P, NP, etc

The standard complexity classes such as P, NP are usually defined using Turing Machines. In finite model theory those classes can be defined via the classical first-order/second-order logics.
I am ...

**2**

votes

**1**answer

310 views

### Problem to a solution

Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...

**0**

votes

**1**answer

149 views

### Interaction-based approximation for HP-complete λ-theory?

We are looking for a proof or counter-examples for the following hypothesis.
Two combinators $M$ and $N$ are solvable and equivalent in the HP-complete sensible $\lambda$-theory iff either
$$
\exists ...

**1**

vote

**1**answer

218 views

### Nontrivial, partially uncomputable function

is there any example of function which is computable on some set and uncomputable on other set? That is for example function f(n) which is computable on some (finite, or for example for even numbers) ...

**3**

votes

**1**answer

183 views

### A computability-theoretic preorder on reals

My question is about a fairly artificial preorder on functions from $\omega$ to $\omega$, which for simplicity I'll call "reals."
For $r, s\in {}^\omega\omega$, write $r\le_E^*s$ if for each real $f$ ...

**4**

votes

**3**answers

479 views

### What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?

Let me begin with an example.
Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...

**4**

votes

**1**answer

120 views

### About infinite subset of halting probability and 1-random set

Let $\Omega$ be the halting probability (see (http://en.wikipedia.org/wiki/Chaitin's_constant) and R. Downey, and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity for reference). If A is ...

**0**

votes

**2**answers

575 views

### Game of Chess and axiomatic systems [closed]

Consider a deterministic, perfect information, abstract strategy, finite game , with absurdly large state space, say ...chess
Q1 Is the game translatable to an axiomatic system?
Q2 Can all ...

**0**

votes

**3**answers

376 views

### Random infinite sequence : Can machines generate truly random sequences. [closed]

Test : "A True Random Sequence Source and a computer producing a certain sequence of numbers are kept in separate rooms and judges try to tell them apart by conducting a series of tests on the ...

**25**

votes

**1**answer

759 views

### Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
...

**0**

votes

**1**answer

221 views

### Random infinite sequences

An Algorithm/Turing machine
Produces a symbol from a finite alphabet, and continues doing so
infinitely.
Another algorithm gets a copy of this symbol,
...

**3**

votes

**1**answer

125 views

### What is the Arithmetical complexity of determining whether a 2-ary computable predicate has exactly one infinite column

Let $W_e$ be the $e$th computably enumerable set in a standard enumeration. For $A\subseteq \omega$, let $A^{[i]}:=${ $ a : \langle a,i\rangle \in A$}. What is the arithmetical complexity of {$e : ...

**2**

votes

**1**answer

141 views

### Question about undecidable consequences of Con, learnability and arithmetical complexity of logical consequence

Let$\:$ $T=\{\varphi \in \Pi_1: PA+Con(PA) \vdash \varphi\:\:and\:\: PA\nvdash \varphi \}$. $\:$By the facts presented here Are undecidable consequences of Con recursively enumerable? by Andreas ...

**5**

votes

**1**answer

536 views

### What can be done with computability logic that previous logic systems can't?

I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics.
What I'm seeking to know is:
Can computability logic ...

**3**

votes

**2**answers

248 views

### Computability complexity of the first-order theory of arithmetic?

Hello,
It's well known that Kleene's O is $\Pi^1_1$-complete. Does the same thing go for the first-order theory of arithmetic? (I'm talking specifically without set quantifiers---the theory of ...

**19**

votes

**3**answers

2k views

### Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Assume for this question that ZF set theory is sound.
Now consider the language "PROVELOOP," which consists of all descriptions of Turing machines M, for which there exists a ZF proof that M runs ...

**16**

votes

**1**answer

1k views

### Lawvere's fixed point theorem and the Recursion Theorem

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\implies ...

**5**

votes

**1**answer

348 views

### Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...

**5**

votes

**1**answer

370 views

### First order consequence of a combinatorial principle

(Base theory $RCA_0$)The principle says there exists a function g such that g dominates any X-recursive function for any X in the model.
i.e. For any $f\le_T X$, $\exists b\in M$ such that ...

**14**

votes

**5**answers

1k views

### Are the two meanings of “undecidable” related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". I regard the ...

**2**

votes

**0**answers

142 views

### Reference for original paper (but translated to English) of Matiyasevich's proof of Fibonacci relation being Diophantine?

Hello. I am a maths undergraduate. I am doing a project about history of mathematics. I am looking for the original solution to Hilbert's 10th problem, or at least the theorems that is accessible to ...