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

4
votes
1answer
212 views

The word problem of the free left distributive algebra on one generator

A left distributive algebra is a set $A$ together with a binary operation, $\cdot$, satisfying $a\cdot(b\cdot c)=(a\cdot b)\cdot(a\cdot c)$. One important example of left distributive algebras arises ...
2
votes
0answers
161 views

Both NP-hard but different [closed]

What's the fundamental difference between the Knapsack problem and the travelling salesman (TSP) problem both of which are NP-hard, while the reality is that TSP could be solved much much faster?
3
votes
1answer
68 views

Are lightface \Delta-1-1 classes of reals describable with hyperarthmetic formulae?

I'd appreciate if someone could check my reasoning. Suppose $S$ is a lightface $\Delta^1_1$ class of reals. I want to argue that there is a computable $\Delta^0_\alpha$ formula $\phi(Y)$, for ...
8
votes
1answer
278 views

Infinite decreasing sequence by the Turing jump

I saw in Wikipedia the existence of an infinite sequence of Turing degrees $\bf{a_0}, \bf{a_1}, \dots$ such that $\bf{a}_{i+1}' \leq_T \bf{a}_i$ where $\bf{a}_{i+1}'$ is the Turing jump of $\bf{a}_i$. ...
3
votes
1answer
508 views

Some types of diophantine equations and their decidability

The MDRP theorem – which answers Hilbert's tenth problem in the negative – says: There is no algorithm for determining whether an arbitrary diophantine equation has a solution. In ...
8
votes
2answers
252 views

Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?

A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
-3
votes
1answer
133 views

Randomness about coefficients of series

$B\subset \mathbb{N}\bigcup \{0\}$ is finite and not empty, infinite series:$$f(x)=\sum_{i=1}^{\infty}a_i x^i,a_i \in B$$ Now $f(x)$ is rational or has a natural boundary. Now,the question :if ...
10
votes
1answer
467 views

Does Turing determinacy imply full determinacy?

The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined. In "Turing ...
12
votes
1answer
413 views

Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?

Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
11
votes
1answer
445 views

Higher recursion theory and reverse mathematics: What is to $\Pi^1_1-CA_0$ as $RCA_0$ is to $ACA_0$?

There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" - indeed, this is the starting point of metarecursion theory, and $\alpha$-recursion theory in ...
5
votes
1answer
371 views

Uncountable time Turing machines

When writing with a friend of mine today we came up with idea of extending ITTM concept of Hamkins and Kidder. First of all, I am familiar with one of Hamkins and Lewis results saying that every ...
6
votes
1answer
312 views

Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
2
votes
3answers
773 views

An established proof in Wang Tile which I doubt

When I was reading the paper: Wang, Hao. "Notes on a class of tiling problems." Fundamenta Mathematicae 82.4 (1975): 295-305. from http://matwbn.icm.edu.pl/ksiazki/fm/fm82/fm82119.pdf I could not ...
7
votes
1answer
359 views

Demuth's theorem in set theory

I am quite sure the following fact must have been known for set theorists, though I could not find it anywhere. If $r$ is random over $L$ and $x\in L[r]\setminus L$, then there must be some real ...
9
votes
0answers
212 views

Infinite time game of life

Today in a talk with a friend of mine I had an idea of extending cellular automatons to transfinite working time. I know it has already been considered, but, as far as I can tell, GoL extended to ...
4
votes
1answer
290 views

Necessity of omega-models in second order arithmetic

Are there examples of independence results over subsystems of true second order arithmetic that cannot be established using omega-models? To rule out trivial examples, let us assume that the base ...
1
vote
1answer
50 views

How to select a subset of points from a universal to minimize the distance from outside to inside?

Here is the detailed problem. I have a set of N points in K-dimension space, called U, and I want select M points of them, called S. For each point p in U, we define the distance from p to S as $$ ...
6
votes
2answers
253 views

Only admissibles start gaps in clockable ordinals

This is a question about ITTM model introduced by Hamkins et al. In this paper it is proven that no admissible ordinal is clockable, so it either starts or lies within a gap in clockable ordinals. I ...
5
votes
1answer
225 views

Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function “Abit” primitive recursive?

Example of "Abit": Ack$(2,3)=9=1001_2$ (base 2). Thus Abit(2,3,3)=1 (the leftmost bit of $1001$. The index of the rightmost bit is 0) Question 1: Is the function "Abit" primitive recursive (PR)? ...
5
votes
4answers
547 views

Are there natural, small, and total recursive functions that are not primitive recursive?

In a sense the Ackermann function is not primitive recursive (PR) because it grows too fast. Are there total recursive, not PR, small functions? Using a diagonal argument, we may define a total ...
19
votes
1answer
717 views

Why isn't this a computable description of the ordinal of ZF?

In a previous MO question, I was told by several commenters that (a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
15
votes
0answers
272 views

Computability of Brauer groups

A friend of mine and I were talking about computable algebra, and this question came up. The answer may already be known, but I couldn't find it with Google: Suppose I have a countable field, $k$. ...
15
votes
3answers
604 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 ...
10
votes
1answer
358 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 ...
6
votes
1answer
693 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 ...
1
vote
1answer
195 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 ...
1
vote
0answers
113 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 ...
3
votes
1answer
400 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 ...
3
votes
2answers
196 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 ...
8
votes
1answer
220 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 ...
5
votes
1answer
265 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$ ...
2
votes
2answers
210 views

Absolutely algorithmically random infinite sequence

Let's call an infinite sequence of bits $f:N\rightarrow \{0,1\}$ absolutely random if any computably constructed subsequence is not computable, i.e. there aren't monotonic computable function $g:N ...
9
votes
2answers
493 views

What is the precise notion of “enough arithmetic” in Godel's first Incompleteness theorem?

I'm trying to reconstruct the proof of Godel's first theorem (Rosser's strong version) from the uncomputability of the Halting function. If we just started with the language $\mathcal{L}=\{0, S, +, ...
-1
votes
1answer
207 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 ...
3
votes
1answer
264 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 ...
5
votes
6answers
778 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 ...
3
votes
1answer
149 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 ...
12
votes
0answers
321 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 ...
6
votes
2answers
269 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 ...
1
vote
1answer
214 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 ...
5
votes
1answer
133 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 ...
8
votes
3answers
714 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 ...
7
votes
2answers
464 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 ...
1
vote
1answer
128 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 ...
9
votes
3answers
383 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 ...
7
votes
2answers
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 ...
9
votes
4answers
545 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
227 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 ...
3
votes
1answer
222 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 ...