**19**

votes

**1**answer

820 views

### Word problem for fundamental group of submanifolds of the 4-sphere

Given any finitely-presented group $G$, there are a few equivalent techniques for constructing smooth/PL 4-manifolds $M$ such that $\pi_1 M$ is isomorphic to $G$. For most constructions of these ...

**3**

votes

**1**answer

114 views

### A question on many-one reducibility

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. For each $x\in\mathbb{N}$, let $W_x$ the domain of $\phi_x$, and let $K=\{x\in\mathbb{N}:W_x\neq\emptyset\}$. Is there a ...

**-4**

votes

**0**answers

36 views

### Hamiltonian Tour with Machine A and B [closed]

I ran into a question on previous Mid-Exam. anyone could clarify me?
Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight.
Problem B: Given a Complete Weighted ...

**6**

votes

**1**answer

194 views

### What is known about the boundary between Richardson's theorem and the Tarski-Seidenberg theorem?

Tarski proved that equalities and inequalities in can be decided over $\mathbb{R}[x].$ Richardson proved that adding composition with the sine and exponential functions caused the problem to become ...

**2**

votes

**2**answers

150 views

### Computable Categories in the most direct sense?

While there is a lot of work in category related to notions of realizability and computability, etc... I've failed to find work on categories that are computable in the sense of having object and ...

**1**

vote

**1**answer

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

**0**

votes

**1**answer

174 views

### Is there a nontrivial maximally recursive function? [closed]

Say that a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ is maximally recursive if, for all $n\in\Bbb N$, the value $f(n+1)$ can be calculated only by first knowing $f(n)$. A rather trivial example ...

**14**

votes

**5**answers

1k views

### Are the two meanings of “undecidable” related?

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". I regard the ...

**12**

votes

**0**answers

207 views

### The topos for forcing in computability theory

My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site."
My ...

**7**

votes

**2**answers

232 views

### Decidability of diophantine equation in a theory

Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows:
Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether
...

**7**

votes

**2**answers

204 views

### Recent trends in effective analysis

The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...

**-1**

votes

**1**answer

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

**45**

votes

**8**answers

5k views

### Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge:
You have fifteen seconds. Using standard math notation, English words, or both, name a single ...

**22**

votes

**0**answers

628 views

### On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...

**5**

votes

**2**answers

311 views

### TM and abstract algebra

Usually, during lectures Turing Machines are firstly introduced from an informal point of view (for example, in this way: http://en.wikipedia.org/wiki/Turing_machine#Informal_description) and then ...

**1**

vote

**2**answers

215 views

### Is there a pairing function from countable ordinals to $\mathbb N$? [closed]

It is well-known that there is a computable pairing function $<\ >:\mathbb N^2\to \mathbb N$. Let $X$ be some reasonable class of countable ordinals ($\omega_1^{CK}$, $\epsilon_0$, ...

**18**

votes

**5**answers

2k views

### Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only.
When I learnt to the topic of relativization ...

**10**

votes

**1**answer

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

**12**

votes

**1**answer

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

**5**

votes

**0**answers

63 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

195 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

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

**4**

votes

**1**answer

71 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

268 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

267 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

186 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

417 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

17k 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

312 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

61 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

173 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

201 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

796 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

154 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

76 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

327 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

186 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

228 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

657 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

101 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

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

**-3**

votes

**1**answer

280 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

106 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

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

**82**

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

207 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

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