**4**

votes

**3**answers

566 views

### “Rice (like) Theorem” for primitive recursive functions?

As primitive recursive (PR) functions seem to be so important
(see for instance Kleene normal form Theorem) we may expect that
many decision questions related to PR functions are undecidable.
...

**3**

votes

**2**answers

479 views

### Are there proofs of Rice Theorem without using the undecidability of some problem?

Most proofs of Rice theorem seem to be based on the undecidability of
the halting problem. They are "reduction-based".
Are there "direct" elementary proofs, perhaps based on diagonalization?
I think ...

**9**

votes

**0**answers

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

**63**

votes

**2**answers

2k views

### How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually ...

**6**

votes

**1**answer

127 views

### Is 0' of PA degree relative to a non-low set?

Definitions:
A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path.
A set $X$ is low if $X'$ is computable from ...

**2**

votes

**0**answers

96 views

### What are natural examples of non-relativizable proofs? [duplicate]

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles).
Virtually all proofs seem to be relativizable, though.
What are good examples of ...

**3**

votes

**1**answer

121 views

### Is there a Turing degree which is a strong minimal cover and does not have itself a strong minimal cover?

We say that a Turing degree $a$ is a strong minimal cover of $b$ if $a$ is strictly above $b$ and if any $c$ strictly below $a$ is (not necessarily strictly) below $b$. It is known that some degrees ...

**3**

votes

**1**answer

73 views

### Jump of strongly hyperhyperimmune degrees and DNR relative to 0'

A function f is diagonaly non-recursive (DNR) if for every Turing index $e$, $f(e) \neq \Phi_e(e)$.
A set is strongly hyperhyperimmune if there is no r.e. set of disjoint r.e. set intersecting it.
...

**26**

votes

**10**answers

3k views

### Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...

**10**

votes

**1**answer

858 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

138 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

328 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

850 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

365 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

282 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

429 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

439 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

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

**5**

votes

**1**answer

237 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

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

**2**

votes

**0**answers

86 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

259 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

900 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

377 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

202 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

170 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

380 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

249 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

506 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

189 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

388 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

193 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

194 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

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

**29**

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

**22**

votes

**1**answer

589 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

424 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

168 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

312 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

236 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

186 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

493 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

587 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

383 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

768 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

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