**3**

votes

**1**answer

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

**3**answers

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

**1**answer

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

**4**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

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

**5**

votes

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**2**answers

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

**4**answers

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

**3**answers

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

**2**answers

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

**1**answer

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

**1**answer

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

**3**answers

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

**3**answers

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

**3**answers

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

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

**24**

votes

**15**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**4**answers

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

**3**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**1**answer

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