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

6
votes
2answers
205 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
177 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
175 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 ...
44
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
606 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
302 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
1answer
118 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 $. ...
1
vote
2answers
209 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
502 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
507 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
6answers
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
0answers
61 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
1answer
191 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
0answers
65 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
65 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
265 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
260 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
180 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
411 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
16k 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
306 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
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
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
198 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
795 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
153 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
73 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
326 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
0answers
185 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
1answer
221 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
654 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
2answers
99 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
1answer
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
1answer
273 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
0answers
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
2answers
283 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
42answers
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
3answers
201 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
1answer
74 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
1answer
126 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
1answer
134 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
0answers
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
0answers
152 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
1answer
60 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
2answers
237 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
1answer
268 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
1answer
492 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 ...