# Tagged Questions

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

648 views

### Which distributions can you sample if you can sample a Gaussian?

Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...
602 views

### Is this property equivalent to Lusin's property (N) for continuous functions?

A function $F:[0,1]\rightarrow\mathbb{R}$ satisfies Lusin's (N) property if for every measure zero set $A\subseteq [0,1]$, $F(A)$ has measure zero. (This includes the assertion that $F(A)$ is ...
1k views

### Is rule 30 Turing complete? Is there a proof that it isn't?

It is well known that the elementary cellular automaton known as rule 110 is Turing complete. Its cousin rule 30 also produces complicated behaviour. When I read Wolfram's a New Kind of Science (in ...
276 views

### relationship between corner tile and edge tile of wang tile

It is clear that any corner type of Wang Tile could be converted to edge type of Wang Tile by defining the edge color according to the corner color. However, could we convert edge type of Wang Tile ...
127 views

### Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
429 views

### Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
208 views

### Conjecture of a subset of Wang tile which might be decidable

From the two papers proving the undecidability of Wang tile in 1966 by Berger and in 1971 by RM Robinson, the tiles used in proving undecidability has a general common feature: The left color and ...
243 views

### Martin-Löf randomness relative to a $\Delta^0_2$-representation of a real

I have a question which I already asked on a more specialized site (http://logicblogfrontend.hoelzl.fr/), but perhaps M.O. will allow me to reach a wider range of experts. Suppose that $X$ is Martin-...
340 views

### Interaction between Turing and many-one reducibility

This is a question about two reducibility notions in computability theory. I suspect the answer is a fairly simple construction, and I'm just not seeing it. For sets $X, Y\subseteq\omega$, we say $X$ ...
231 views

318 views

### What is the probability that a randomly chosen number from set of c.e.number is period(number)?

What is the probability that a randomly chosen number from the set of c.e.numbers is period(number)? What is the probability that a randomly chosen number from the set of computable numbers is ...
295 views

### What is the relation between KC and height of rational number?

Roughly speaking,Kolmogorov Complexity of a bits string or a description is the minimal length of programs outputing a bits string,and height of rational number is logarithm of the largest numerator ...
906 views

### practical algorithms for np complete problems

Inspired by: Conjecture on NP-completeness of tesselation of Wang Tile up to finite size And the practicality of this topic (solving tessellation on a lattice): coloring in lattice Computational ...
170 views

### Decidability of prime gap sequences

Is the following problem undecidable? Given a sequence of $n$ gaps $d_1,d_2,...,d_n$, does there exist a sequence of $n+1$ primes $p_1,p_2,...,p_{n+1}$ such that $p_{i+1} - p_i = d_i$ ? If not, is ...
343 views

### Do all linear orders in this class have computable copies?

This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
306 views

### Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the Halting problem, are complete in $\Sigma_1$, relatively to the many-to-one reduction. In fact I don't know any example of a (non ...
269 views

### Would a non-constructible set become constructible if we had oracles of arbitrarily high cardinality for the halting problems of ordinal computers?

I still have trouble to grasp the concept of a non-constructible set, my intuition is that we could "avoid" the non-constructibility of many of them if we assume we have "ordinal computers" extended ...
140 views

### Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of ...
920 views

### What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
469 views

### What is the name of this type of groups?

Suppose $A$ is a finite set and $\Sigma=A\cup A^{-1}$. Let $L\subseteq \Sigma^{\ast}$ be a regular language on the alphabet $\Sigma$. Is there a common name for the group $G$ presented as: G=\langle ...
149 views

### Every infinite C.E.language is infinite or finite union of regular languages including at least one infinite regular language?

Is Every infinite C.E.language infinite or finite union of regular languages including at least one infinite regular language? And is every infinite C.E.language that is not indexed language(that may ...
435 views

### Conjecture on NP-completeness of tesselation of Wang Tile up to finite size

Motivated by these following questions on tessellation: coloring in lattice Reference for Wang Tile Computational approach deciding whether a set of Wang Tile could tile the space up to some size ...
1k views

### Is Turing degree actually useful in real life? [closed]

In theoretical computer science, we classify problems according to their Turing degree. Is there any practical application of this? Edit: Given that we cannot explicitly and mechanically understand ...
634 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 ...
249 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 ...
239 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 ...
140 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 ...
432 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 ...
105 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 $M$....
607 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. ...
523 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 ...
395 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 ...
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 ...
138 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 $\emptyset'$....
97 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 ...
129 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 ...
76 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. ...
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$ ...
916 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 ...