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

2
votes
0answers
89 views

Comparing two non-deterministic Turing equivalents as basis for Logic, request for references

I am designing a logic, that is simpler than FOL + PA. And I like to know if there already exists something in this direction. First of all a non-deterministic Turing equivalent is defined by ...
4
votes
0answers
85 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 ...
3
votes
2answers
227 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
214 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 ...
8
votes
0answers
299 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 ...
56
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
97 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
92 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
92 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
68 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. ...
24
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
701 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
112 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
89 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
223 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
451 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
334 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
176 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$ ...
4
votes
3answers
398 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 ...
10
votes
1answer
312 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
93 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
209 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
258 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
72 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
246 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
782 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
279 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
194 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
158 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
285 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
195 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
351 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
140 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 ...
8
votes
2answers
345 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
103 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
150 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
278 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
3answers
1k 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 ...
17
votes
1answer
346 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
244 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
112 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
293 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
143 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
164 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
162 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
365 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
1answer
101 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
2answers
424 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
3answers
300 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 ...
23
votes
1answer
675 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 ...