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

-1
votes
0answers
58 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 ...
29
votes
2answers
869 views

Does an existence of large cardinals have implications in number theory or combinatorics?

Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
13
votes
7answers
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 ...
7
votes
1answer
208 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
0answers
88 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: ...
3
votes
1answer
205 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 $$ ...
0
votes
0answers
54 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 ...
4
votes
3answers
377 views

“Rice (like) Theorem” for primitive recursive functions?

As primitive recursive (PR) functions seem to be so important (see for instance Kleene normal form Theorem) we may expect that many decision questions related to PR functions are undecidable. ...
4
votes
2answers
214 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 ...
1
vote
1answer
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 $. ...
3
votes
1answer
183 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
1answer
345 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
1answer
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$ ...
19
votes
1answer
827 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
1answer
136 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 ...
6
votes
1answer
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 ...
2
votes
2answers
156 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 ...
0
votes
1answer
180 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
5answers
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
0answers
230 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
2answers
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 ...
7
votes
2answers
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 ...
-1
votes
1answer
187 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
8answers
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
0answers
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
2answers
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
2answers
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$, ...
18
votes
5answers
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
1answer
530 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
1answer
527 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
0answers
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?
0
votes
0answers
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
1answer
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
3answers
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
1answer
274 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
2answers
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
2answers
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$ ...
22
votes
4answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
3answers
800 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
0answers
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
0answers
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
1answer
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
1answer
233 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
5answers
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 ...