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

3
votes
1answer
246 views

Proof of the existence of hyperimmune-free degrees

In Classical Recursion Theory Vol.I by P.Odifreddi, section V.5 on the Tree Method, the proof for the existence of hyperimmune-frees involves the construction of a series of trees. Some definitions ...
4
votes
3answers
303 views

Existential quantification over regular predicates

A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...
4
votes
1answer
215 views

Reference for a “recursive” fragment of infinitary logic?

Does anyone know of any texts or papers out there concerning properties of the fragment of $ \mathcal{L}_{\omega_1, \omega} $ in which the only admissable infinite conjunctions are those which are ...
20
votes
4answers
1k views

Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...
3
votes
2answers
1k views

Is there an algorithm that can “reverse engineer” a Regular Expression?

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?
6
votes
3answers
646 views

computational complexity of primitive recursive functions

If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
3
votes
1answer
285 views

Diagonalization and classes of computable functions

Fix a standard effective listing $(\phi_e)_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow ...
6
votes
1answer
390 views

Probability that a Turing machine will nontrivially reduce a real

For a fixed Turing machine $\Phi_e$, what is the probability that it will reduce a given real to some less complex, yet still non-computable real? More precisely: It is known that the set of reals ...
3
votes
2answers
339 views

Representation of μ-recursive functions

Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function? According to Wikipedia, any μ-recursive function can be expressed as the ...
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 ...
5
votes
1answer
546 views

Countable admissible ordinals

Jensen claimed that for any finite increasing sequence countable admissible ordinals $\omega= \alpha_0<\alpha_1\cdots <\alpha_n$, there is a real $x$ so that, for each $m\leq n$, $\alpha_m$ is ...
3
votes
0answers
95 views

Is a parametric family which is universally consistent for multiple quantiles impossible?

Suppose I am dead-set on using Bayesian inference on independent and identically distributed data, but I'm lazy and insist on using a parametric likelihood function come what may. I'd be reassured to ...
5
votes
1answer
279 views

Higher computability : Constructive ordinal and $\Delta^1_1$ predicates

Everything I know on this subject comes from Sacks book : "Higher recursion theory" Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$. We should have the result that $A ...
6
votes
2answers
901 views

Busy Beaver - Proof for BB(2) = 4

Hi, I need to prove the above claim. I can show that $BB(2)\ge 4$ by building a turing machine, but how can i show that $BB(2) \le 4$? Searched a lot over the web, and saw that Rado proved it in ...
4
votes
0answers
265 views

Difference between lambda-calculus with well-formed formulas vs properly-formed formulas

In S.C. Kleene's 1935 paper "$\lambda$-definability and recursiveness," he proves that all $\lambda$-definable functions are general recursive in the Herbrand-Godel sense and vice-versa. However, the ...
3
votes
2answers
694 views

Kleene's fixed point theorem on recursive subsets of computable functions

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...
4
votes
1answer
452 views

Infinite monkeys computing … triangle area?

I wonder if it is possible to specialize the question: (a) What is the probability that a random Turing Machine program will halt?, to: (b) What is the probability that a random Turing Machine ...
10
votes
2answers
492 views

What is the computational-complexity-theoretic analogue of computable inseparability? For example, if P is not NP, are there disjoint NP sets with no separation in P?

Disjoint sets $A$ and $B$ are computably inseparable, if there is no computable separating set, a computable set $C$ containing $A$ and disjoint from $B$. The existence of c.e. computably inseparable ...
12
votes
1answer
611 views

Does every feasible partial order relation on the natural numbers extend to a feasible linear order relation?

It is well known that every partial order on a set can be extended to a linear order on that set. That is, for every partial order $\lhd$ on a set $X$, there is a linear order $\prec$ on $X$ such that ...
54
votes
3answers
5k views

Can a group be a universal Turing machine?

This question was inspired by this blog post of Jordan Ellenberg. Define a "computable group" to be an at most countable group $G$ whose elements can be represented by finite binary strings, with the ...
2
votes
1answer
182 views

Is this c.e. set obtained via the Recursion Theorem?

Reading through a text on computability I came across a c.e. set defined as follows: Let $K=\lbrace x \in W_x \rbrace$ and let $f$ be a computable function. Then there exists $n \in \omega$ such that ...
1
vote
1answer
98 views

Turing code numbers and c.e. sets.

Let $W_e$ be the c.e. set which is the domain of the p.c. function $\varphi_e$ and consider the equivalence $\sim$ such that $x \sim y$ if and only if $\varphi_x=\varphi_y$. I am wondering if $W_e$ ...
1
vote
1answer
337 views

Infinite set with/without infinite c.e. subsets

Let $\varphi_e$ denote the p.c. function computed by the Turing Machine with code number $e$. I am looking at the set $M = \lbrace x : \neg (x < y)[\varphi_x=\varphi_y] \rbrace$. This set is ...
3
votes
2answers
257 views

$\Delta_2$-inseparability?

Since long ago it is known the existence of non-recursive sets (i.e., non-$\Delta_1$), e.g., Halting problem. It is also known (firstly noticed by Trakhtenbrot, and deeply studied by Smullyan) the ...
2
votes
1answer
711 views

What about the fastest-growing non-computable function ?

The Busy-Beaver trick provides a nice example of non-computable functions (let say from $\mathbb{N}$ to $\mathbb{N}$) which grows faster than any computable functions. But what can we say when we do ...
9
votes
2answers
344 views

Can we represent computable functions by r.e. sets ?

As we know, if $f$ is a computable function, then every pre-image of a r.e. set under $f$ is also a r.e. set, i.e. $f^{-1}(X)$ is a r.e.set if $X$ is a r.e. set. So I want to know that if a function ...
5
votes
4answers
2k views

Explicit expression for recursively defined functions

Consider a function $w(i)$, $i \in \mathbb{N}$, defined recursively by: $w(0)=w(1)=1$, and $w(i)={i}^{n}-\sum_{j=1}^{i-1}{i \choose j}w(j)$ for $i>1$. Is it possible to write $w(i)$ out ...
9
votes
3answers
792 views

Effective topos and computability in topological spaces

The classical computability theory taking place in $\mathbb{N}$, can be extended to more general spaces, like $T_0$ second countable topological spaces $(X, \mathcal{O}, v)$ where $\mathcal{O}$ is a ...
6
votes
2answers
474 views

Natural statements independent from true $\Pi^0_2$ sentences

I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
2
votes
1answer
322 views

On families of finite graphs with undecidable first-order theory

It is well known that the first order theory of graphs (i.e., an irreflexive and symmetric "edge" relation on a set) is undecidable. The same holds for the first order theory of finite graphs. I am ...
0
votes
1answer
151 views

any given c.e.set has number M whose power bounds the corresponding elements of S?

For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq ...
8
votes
3answers
1k views

Undecidable problems in geometry

Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry? Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...
19
votes
3answers
1k views

Inverse Ackermann - primitive recursive or not?

I wanted to put this originally on math.stackexchange, since I considered it to be a straightforward question and probably a fairly known fact. After I failed to solve the problem, I browsed through ...
1
vote
3answers
437 views

Variant of the usual proof method for undecidability of the halting problem

This is a largely a question of pedagogy/references, though I may have overlooked some nuance of actual mathematics. I am planning to introduce the concept of Turing machines and the halting problem ...
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 ...
24
votes
15answers
4k views

What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less ...
13
votes
1answer
650 views

Are wild problems related to undecidable ones?

In representation theory, there is a well-known notion of a wild classification problem (such problems have been discussed often on this forum, for example, here). In logic, there is a notion of an ...
0
votes
1answer
648 views

When may Function (meromorphic) be expanded as power series with coefficients of integers

Let F be meromorphic function,with what properties may it expanded as power series with coefficients of integers in such a form: $$F=\sum_0^{\infty}a_i x^i,a_i\in \mathcal{N} \bigcup 0,\exists M ...
3
votes
1answer
296 views

Paths in Kleene's O and deciding $\Pi^0_1$ sentences

This question comes from the Wikipedia article on Kleene's O and a previous Math Overflow question. The claim in Wikipedia that I have a question about is the second sentence in the following quote. ...
5
votes
1answer
508 views

Machine model for primitive recursion?

General computable functions can be described either functionally (in terms of closure of the coordinate functions, constant functions, composition, primitive recursion, and $\mu$-recursion), or in ...
3
votes
1answer
423 views

Hyperarithmetic statements decidable by induction up to a recursive ordinal

The first version of this question received a helpful answer but was too vague to fully convey what I intended. I hope this version remedies that problem. For any hyperarithmetic set of integers $S$, ...
6
votes
4answers
258 views

What sets are “decidable from competing provers”?

Let $n$ be a member of $\omega$, which the omnipotent provers $Y$ and $N$ know. A Turing machine will be run starting with the $n$ already inputted, and the machine can have a natural number inputted ...
2
votes
3answers
397 views

Code universal arithmetical sets by a hyperarithmetical set?

For each n, there is a (lightface) Σ0n set Sn ⊆ ω2 that's universal for the Σ0n subsets of ω. Since {n} × Sn is Σ0n, there is a union R of arithmetical ...
7
votes
3answers
1k views

Can the twin prime problem be solved with a single use of a halting oracle?

It occurred to me that if it were possible to determine whether a given program halts, that could be used to answer the twin primes conjecture A) Write a program which takes input n and then counts ...
2
votes
1answer
1k views

How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
4
votes
1answer
286 views

Hyperarithemtic statements decidable by induction up to a recursive ordinal

Kleene's O is a $\Pi_1^1$ complete set that decides every hyperarithmetic statement. A Turing Machine that uses this set as an oracle to decide a hyperarithmetic question can only look at a finite ...
11
votes
0answers
469 views

Diagonal lemma from recursion theorem?

Does Gödel's diagonal lemma follow from Kleene's recursion theorem? I believe the converse is true, by an argument like the following. Let e ↦ θe be a bijection between ω and ...
15
votes
1answer
706 views

Undecidable theories easier than $Q$

Most proofs of undecidability for various theories (pure logic with binary relation, group theory, etc.) show that the natural numbers and Robinson's $Q$, in one form or another, can be encoded ...
4
votes
2answers
502 views

Existence of a set of valid Busy-Beaver entries.

In reference to 1961 paper "On Non Computable Functions" by T. Rado. Motivation - Scott Aaronson's Who Can Name the Bigger Number?. M is an n-state binary Turing machine. A valid BB-n entry is a ...
9
votes
1answer
2k views

Kolmogorov Complexity and Proof Techniques

I'm interested in examples of theorems that employ the proof techniques that are utilized in the proof of the undecidability of Kolmogorov Complexity. Definition:(Sipser) Let x be a binary string. ...