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

learn more… | top users | synonyms

9
votes
4answers
558 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 ...
4
votes
1answer
230 views

N^2 and two counter machines

I asked this question on cstheory a few months ago, but I didn't receive an answer, so I'm posting it here to see if there are original ideas from the "math world" to solve it. The original question ...
4
votes
1answer
225 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
4
votes
1answer
134 views

Self-similarity in the theory of computability

Let $M = w_0w_1... \in \{0,1\}^*$. For any computable function $f$ define $M_f = w_{f(0)}w_{f(1)}...$ Let for any computable strictly increasing function $f$ there is continuous computable mapping ...
4
votes
2answers
404 views

Reverse Math of High Sets?

Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to ...
4
votes
0answers
93 views

Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in ...
4
votes
3answers
468 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
2answers
403 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
0answers
350 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 ...
62
votes
2answers
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
1answer
113 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
0answers
93 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
1answer
113 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
1answer
71 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
10answers
2k 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
1answer
789 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
1answer
128 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
0answers
121 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
0answers
296 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 ...
5
votes
2answers
628 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
2answers
356 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
3answers
235 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
3answers
421 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
1answer
390 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
1answer
95 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
1answer
226 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
2answers
278 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
0answers
84 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
0answers
252 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
4answers
844 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
1answer
346 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
1answer
197 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 ...
6
votes
1answer
166 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
3answers
343 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
1answer
226 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
2answers
437 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
3answers
176 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
2answers
378 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, ...
1
vote
0answers
133 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
1answer
188 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
1answer
306 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 ...
27
votes
3answers
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 ...
20
votes
1answer
517 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
1answer
353 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
1answer
134 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
1answer
308 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
1answer
148 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
1answer
203 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
1answer
170 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
3answers
442 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$, ...