**0**

votes

**1**answer

64 views

### Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand ...

**0**

votes

**0**answers

63 views

### Linkage between homotopy equivalence and identification of algorithms

I vaguely recall that someone says there is linkage between homotopy equivalence and identification of algorithms which may be isomorphic or morphism or something like that,the algorithm may be ...

**2**

votes

**2**answers

127 views

### How to define the input of computable function or Turing machine over real numbers

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...

**0**

votes

**0**answers

27 views

### A Simple Uncomputable Function? [migrated]

Let F denote a computable function which
takes an integer and returns an integer. Is "checking whether F has a finite null space"
computable (using an algorithm which works for any F)? I believe ...

**7**

votes

**4**answers

509 views

### (reference request) Chaitin's constant is incompressible

I've been looking for a full, detailed proof that Chaitin's constant is incompressible, i.e. there is a universal constant $c$ such that every program writing first $n$ digits of $\Omega$ has length ...

**2**

votes

**1**answer

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

**3**

votes

**0**answers

141 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

**1**answer

51 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

**1**answer

243 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

**2**answers

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

**7**

votes

**2**answers

193 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

**1**answer

122 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

**1**answer

421 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

**1**answer

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

**10**

votes

**1**answer

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

**4**

votes

**1**answer

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

**4**

votes

**1**answer

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

**3**

votes

**3**answers

735 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

**1**answer

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

**7**

votes

**0**answers

170 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

**1**answer

168 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

**1**answer

35 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

**2**answers

220 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

**1**answer

182 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)?
...

**4**

votes

**4**answers

442 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

**1**answer

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

**13**

votes

**0**answers

236 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

**3**answers

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

**1**

vote

**0**answers

120 views

### Basis of periodic tiling of Wang tile

Given a set of Wang tile,
Given 3 periodic tiling: A, B, C
We define 3 vector F[A], F[B], F[C]
each vector correspond to the appearing frequency of each type of tiles in the tiling.
Now, we ...

**10**

votes

**1**answer

260 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

**1**answer

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

**2**

votes

**1**answer

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

**2**

votes

**0**answers

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

**4**

votes

**1**answer

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

**4**

votes

**2**answers

186 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

**1**answer

201 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

**1**answer

215 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

**2**answers

175 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

**2**answers

426 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, +, ...

**0**

votes

**1**answer

119 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

**1**answer

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

**6**

votes

**6**answers

641 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

**1**answer

129 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

**0**answers

281 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

**2**answers

226 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

**1**answer

182 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

**1**answer

116 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

**3**answers

602 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

**2**answers

454 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

**1**answer

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