**7**

votes

**1**answer

410 views

### Is forcing computable?

By results similar to Tennenbaum's theorem we know that there exist no computable models of $ZF$. But suppose we are given, as a sort of oracle, access to some model of $ZF$ (e.g. we can make oracle ...

**1**

vote

**1**answer

107 views

### Total conditional complexity

By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...

**11**

votes

**1**answer

463 views

### Is there a known primitive recursive upper bound on the nth “Zhang prime”

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...

**13**

votes

**6**answers

1k views

### Finding the largest integer describable with a string of symbols of predefined length

(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at ...

**4**

votes

**0**answers

59 views

### TCAs (total combinatory algebras) with oracles

Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?

**3**

votes

**1**answer

183 views

### A (“Rice-like”) conjecture about the decidability of primitive recursive (PR) problems

Question: is the conjecture below true?
Consider decision problems in which the instance is (the PR index, definition,
or LOOP program of) a primitive recursive function.
Denote the PR function (with ...

**0**

votes

**0**answers

62 views

### Counting path generating sentences in a specific formal language

Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language?
For example, we know that if the grammar is context-free ...

**0**

votes

**0**answers

117 views

### NP-completeness of Ising model [migrated]

In this paper:
http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf
It is claimed that calculating partition function of 3 dimensional ising model is NP-complete. But I have a question, ...

**3**

votes

**1**answer

49 views

### Is below every cohesive set a 1-generic?

A set $X$ is called cohesive for $(R_i)_{i\in \mathbb{N}}$ if it is infinite and for each $i$ we have $X\subseteq^* R_i$ or $X\subseteq^* \overline{R_i}$. (Where $X\subseteq^*Y$ means that $X$ is ...

**2**

votes

**3**answers

249 views

### Prove existence of different programs printing each other code

How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?
Update: We could prove via ...

**9**

votes

**1**answer

233 views

### Busy beaver function vs low Turing degrees

Let $BB(n)$ denote busy beaver function. It's well known that $BB(n)$ dominates all computable functions (I'm quite certain it includes partial computable functions too). However, I was wondering if ...

**4**

votes

**2**answers

167 views

### Relation between Turing degrees and functions computable with them

Suppose $A<_T B$ ($A$ is a set computable from $B$ but not vice versa). Is it always the case that there exists a $B$-computable function which eventually outgrows all $A$-computable functions?
Of ...

**-1**

votes

**2**answers

402 views

### Can an algorithm decide whether a program computes all strings? [closed]

I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ ...

**22**

votes

**4**answers

15k views

### How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...

**62**

votes

**2**answers

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

**3**

votes

**1**answer

290 views

### Are there sets which are computable in one model, but uncomputable in another?

Suppose we have two models of set theory, $U$ and $V$ which have the same $\Bbb N$. Is it possible that there is a set $A\subseteq\Bbb N$ such that, in $U$, this set is computable, i.e. there is a ...

**3**

votes

**1**answer

59 views

### The link and equivalence between variant definition of computation model and computational complexity over reals

To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...

**1**

vote

**1**answer

170 views

### The definition of computational complexity or complexity measure of computing reals [closed]

A real $r$ is computable if given any $i\in \mathbb{N}$, the $i$th bit can be outputed by a Turing Machine or an algorithm. So, what is computational complexity or complexity measure of computing the ...

**4**

votes

**1**answer

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

**25**

votes

**3**answers

1k views

### Is it decidable whether or not a collection of integer matrices generates a free group?

Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...

**12**

votes

**3**answers

791 views

### (un)decidability in matrix groups

Given a collection of matrices $S=\{M_1, \dots, M_k\}$ in (say) $SL(n, Z), \ n>2$ does $S$ generate $SL(n, Z)?$
Similar are questions are undecidable for $n\geq 4$ (eg, given a set $S$ as above, ...

**4**

votes

**0**answers

151 views

### Recursively Pointed Sacks Forcing and Preserving $\omega_1$

Let $\mathbb{P}$ denote recursively pointed Sacks forcing. This is forcing with recursively pointed perfect trees ordered by inclusion. A tree $T \subseteq {}^{<\omega}2$ is recursively pointed if ...

**4**

votes

**0**answers

72 views

### Upper bound on ranks of well-founded trees in $SKI\Omega$ calculus

All ideas explained below are due to A.P.Goucher, and defined here.
First of all, $SKI\Omega$ calculus is an extension of standard SKI calculus, with additional type of combinator, called oracle ...

**9**

votes

**1**answer

318 views

### Sets computable from enough hints

Is there a non-computable set $X\subset\omega$ such that, for some $Y\subset\omega$, any infinite subset or cosubset (=subset of the complement) of $Y$ computes $X$?
More generally, call a set $X$ ...

**2**

votes

**0**answers

184 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**3**

votes

**1**answer

212 views

### On fast-growing hierarchy

Is there exists a recursively enumerable set of computable total fast-growing functions $(\mathbb N \rightarrow \mathbb N)$ such, that this set has no upper boundary in the set of all such functions ...

**8**

votes

**5**answers

643 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

**2**answers

93 views

### Background for Kierstead terms

I was looking at some slides of John Longley's here, where he mentions "the Kierstead functional"
$$\lambda f.f(\lambda x.f(\lambda y.x)) \ ,$$
(where $f$ should be of type $2$, and $x,y$ of ground ...

**-2**

votes

**1**answer

87 views

### What are the formula of representation of quasicrystals and the law or mechanism of the formation [closed]

I vaguely recall that formula of representation of quasicrystals is relevant to tiling plane,and tiling plane without period is relevant to recursiveness, and do not know the mechanism or physics ...

**1**

vote

**0**answers

93 views

### reference on aperiodicity and cluster [closed]

From this image:
I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)

**-3**

votes

**1**answer

272 views

### When are two algorithms essentially the same? [closed]

Inspired by Blass/Dershowitz/Gurevich's paper When are two algorithms the same? (which was referenced in another context here) I tried to boil down the question to the following situation:
Consider ...

**3**

votes

**0**answers

104 views

### What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers $\sqrt{A}$ and the integer $A$

What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers and the integer
As we know,$\sqrt{2} = [1;2,2,2,2,…]$; while $\sqrt{14}= ...

**1**

vote

**2**answers

277 views

### Rationale behind an requirement on Turing machines

Hopcroft and Ullman's definition of a Turing machine seems to be standard. This definition defines a Turing machine to be a 7-tupel $T = \langle Q,\Gamma,b,\Sigma,\delta,q_0,F \rangle$ obeying some ...

**81**

votes

**42**answers

17k views

### What are the most attractive Turing undecidable problems in mathematics?

What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...

**2**

votes

**3**answers

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

**1**

vote

**1**answer

61 views

### A possible minimal aperiodic set of corner Wang Tile

From one of my previous question Aperiodic set of corner Wang Tile (although it is put on hold), I realize there is a systematic way to construct aperiodic corner type of Wang tile from edge type ...

**5**

votes

**1**answer

121 views

### Aperiodic set of corner Wang Tile [closed]

There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...

**0**

votes

**1**answer

129 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

72 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

**0**answers

150 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

58 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

**2**answers

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

**8**

votes

**1**answer

265 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

**1**answer

471 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

**3**answers

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

**8**

votes

**1**answer

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

**-3**

votes

**1**answer

129 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

442 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

389 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

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