**5**

votes

**1**answer

59 views

### A decision problem for clones

E. Post proved that there are only countably many clones on a two-element set (classes of operations closed under superposition and containing all projections). All these clones are finitely ...

**-1**

votes

**0**answers

67 views

### Some questions about the paper, “Hypercontractivity, Sum-of-squares Proofs and Their Applications” [on hold]

I am referring to this famous paper, http://arxiv.org/abs/1205.4484
At the top of page 42, the authors define an equation like $f=Gg$, for two functions $f$ and $g$ defined on a graph $G$. This seems ...

**7**

votes

**1**answer

211 views

### Can you decide whether the commutator subgroup of a f.p. group is f.g?

Is the following algorithmic problem known to be decidable/undecidable?
Input: a finite group presentation $P$.
Decide: is the commutator subgroup of the group presented by $P$ finitely generated?

**2**

votes

**0**answers

90 views

### Inverse Ackermann Function

The inverse Ackermann function is defined over the natural numbers as follows: ($[x]$ means that we round up x to the nearest integer, while $\log^*$ is the iterated log function discussed here: ...

**0**

votes

**0**answers

57 views

### How create counterexample for some set in Complexity Theory? [closed]

We know from Martin Davis's book, $K$ is a Halting Set Problem as $K=\{e \mid e \in W_e\}$. $W_e$ is the set of inputs for which the program encoded by $e$ halts.
I read in the book that written ...

**3**

votes

**1**answer

186 views

### Hamkins infinite time Turing machines: dovetailing ordinal time

It is claimed in the Hamkins and Lewis founding article "Infinite time Turing machines" (proof of the gap existence theorem 3.4) that for $\omega$ steps of a computation of a machine performing a ...

**12**

votes

**1**answer

347 views

### Computer software for periods

Kontsevich and Zagier define a period as an integral of a rational function (over $\mathbb{Q}$) defined on a $\mathbb{Q}$-semialgebraic set. They conjecture that if two periods are equal, then the ...

**9**

votes

**1**answer

329 views

### Continuous functions and 2-bushy trees

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison.
A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...

**3**

votes

**1**answer

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

**2**

votes

**2**answers

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

**6**

votes

**1**answer

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

**12**

votes

**0**answers

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

**0**

votes

**1**answer

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

**7**

votes

**2**answers

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

**7**

votes

**2**answers

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

**22**

votes

**0**answers

642 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

318 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

222 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$, ...

**10**

votes

**1**answer

531 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

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

**5**

votes

**0**answers

64 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?

**0**

votes

**0**answers

68 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

72 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

272 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

275 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

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

**4**

votes

**2**answers

194 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

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

**3**

votes

**1**answer

319 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

62 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

**0**answers

161 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

78 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

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

**3**

votes

**1**answer

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

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

**1**

vote

**1**answer

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

**-2**

votes

**1**answer

92 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

109 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

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

**1**

vote

**1**answer

83 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

136 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

139 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

73 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

**3**answers

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

**8**

votes

**5**answers

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

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

**2**

votes

**0**answers

154 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

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