**2**

votes

**1**answer

153 views

### What is the extension of the truth-table degrees to Baire Space called?

Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table ...

**8**

votes

**0**answers

112 views

### Turing degree of finding independent formulas

In this Paper of D. Isaacson, it is proved that the true arithmetic($Th(\mathbb{N}$)) is the only $\omega$-consistent and complete extension of $Q$ (Robinson's arithmetic). This, together the fact ...

**3**

votes

**0**answers

39 views

### Finite realization of irrational transfer functions

In the field of digital signal processing, linear time-invariant systems play a distinguished role. These are the systems for which there exists an impulse response, a function ...

**11**

votes

**4**answers

1k views

### How fast can the base-bumping function in Goodstein's theorem grow?

In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy ...

**1**

vote

**1**answer

108 views

### Computable function [closed]

Let $f(n)$ be
$$
f(n)=\begin{cases}
1,&\small{\text{if there are digits 1 in the constant $\textit{e}$ $\textit{n}$ times in a row}}\\
0,&\small{\text{otherwise.}}\\
\end{cases}
$$
Is it true ...

**10**

votes

**1**answer

347 views

### What Turing degree is this function?

Over at http://www.scottaaronson.com/blog/?p=2725#comment-1089004 we had a discussion of intermediate Turing degrees.
The following function came up:
Take Chaitin’s constant, and rearrange its ...

**-2**

votes

**1**answer

116 views

### Turing and Many one reductions in computability versus complexity

What are some non-trivial (please exclude poly time definitional difference) differences between Turing versus Many-one reductions in computability theory and those that occur in complexity theory?

**7**

votes

**2**answers

707 views

### Complexity of Turing Machine behavior

If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, ...

**8**

votes

**1**answer

285 views

### How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let
$X_{n}$ be the set of all finite sequences of elements from $A_{n}$.
Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting
...

**7**

votes

**2**answers

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

**4**

votes

**5**answers

7k views

### Prove a function is primitive recursive

Hey,
I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I ...

**6**

votes

**0**answers

106 views

### A way to smooth out the log* function?

I have seen here and there discussions about what is the "correct" way of extending the Ackermann function to the reals (the same way the Gamma function extends the factorial function to the reals). ...

**3**

votes

**1**answer

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

**15**

votes

**4**answers

2k views

### Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$.
It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings.
...

**7**

votes

**2**answers

376 views

### Difference between constructive Dedekind and Cauchy reals in computation

If the Axiom of Countable Choice (ACC)
$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)] $$
...

**6**

votes

**1**answer

327 views

### Current status of computable spectral theorem and interpretation of quantum mechanics

The spectral theorem states if $A$ is a Hermitian operator acting on an $n-$dimensional Hilbert space space $H$, and $\lambda_1, ... \lambda_m$ are $m \leq n$ distinct eigenvalues of $A$, then
$$ ...

**3**

votes

**3**answers

167 views

### Coproducts and “Error Conditions” in Math vs CS

First, some background: recently in learning more about functional programming I saw one use for coproducts that surprised me a little bit: A function $f: A \rightarrow B \coprod C$ may result when ...

**4**

votes

**2**answers

221 views

### (non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...

**2**

votes

**0**answers

118 views

### When do wide initial segments ruin admissibility?

Suppose $\alpha$ is admissible and $\beta<\alpha$. We know that $L_\alpha$ is an admissible set (by definition), but adding subsets of $\beta$ to $L_\alpha$ might break admissibility: while set ...

**0**

votes

**0**answers

32 views

### Comparing product of positive affine functions over integers

Problem
Let $f_i: \mathbb Z^n \mapsto \mathbb Z$ and $g_i: \mathbb Z^n \mapsto \mathbb Z$ affine functions and $\mathcal D \subseteq \mathbb Z^n$ a set on which they are all positive. Let $P$ and $Q$ ...

**4**

votes

**1**answer

95 views

### Are these two definitions of arithmetical hierarchy of real numbers equivalent?

Zheng and Weihrauch (http://www-sst.informatik.tu-cottbus.de/~wwwti/zheng/publications/1999/mfcs99.pdf) define a real number $x$ to be $\Sigma_n$ if and only if there is a computable function ...

**12**

votes

**1**answer

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

**2**

votes

**1**answer

500 views

### Can Turing machines clarify mathematical, philosophical, and physical existence?

From Harvey Friedman's manuscript on "Order Invariant Relations and Incompleteness":
DEFINITION 4.4. A $\Pi_1^0$ sentence is a sentence asserting that some given Turing machine never halts at the ...

**6**

votes

**1**answer

257 views

### Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...

**11**

votes

**1**answer

299 views

### Is ordinal arithmetic more complicated than classical arithmetic?

Consider the first-order language $\mathcal{L}_{\text{OA}}:=(+,\cdot,0,1)$; in this language, we can formulate statements of ordinal arithmetic. Clearly, the theory $T_{\text{OA}}$ of ...

**3**

votes

**1**answer

148 views

### Theories of arithmetic from recursively inseparable sets

Edit: all sets / theories considered below are supposed to be recursively enumerable, although I'd also be interested in any possible generalizations to non-enumerable theories.
In the comments on ...

**56**

votes

**8**answers

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

**28**

votes

**5**answers

896 views

### Does the exact pair phenomenon for partial orders occur in your area of mathematics?

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
...

**5**

votes

**1**answer

169 views

### Deciding isomorphism between structures which interpret in the pure set

I am interested in the following decision problem:
Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and ...

**2**

votes

**2**answers

522 views

### Can we compute every definable number with knowledge of the halting problem?

Suppose we knew the answer to the halting problem, and the halting problem for this new system with the old halting problem solved. And so on. Would this allow us to compute every definable number?

**6**

votes

**2**answers

156 views

### a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known.
I need a variant. (For those in the know, I need a c-bar which is ...

**5**

votes

**1**answer

126 views

### “Partial-computably isomorphic” sets

For $A,B \subseteq \mathbb{N}$, define $A\sim B$ when there exist partial computable functions $f,g\colon \mathbb{N}\rightharpoonup \mathbb{N}$ such that $f$ is defined at least on all of $A$ and $g$ ...

**22**

votes

**8**answers

2k views

### Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look ...

**16**

votes

**1**answer

1k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**2**

votes

**2**answers

267 views

### Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...

**0**

votes

**0**answers

98 views

### Distribution of definable integers

Consider the distribution of all formulas of length less then n which define an integer in PA.
So for instance f(7,n)=number of formulas of length less then n which output 7.
Or the number of steps ...

**3**

votes

**1**answer

225 views

### Can we use this symbol? [closed]

We consider the ring $\mathbb{C}[e^{\lambda x} \mid \lambda \in \mathbb{C}]$ and the language $L=\{+, \cdot , \frac{d}{dx} , 0, 1\}$.
The ring consists of elements of the form $$\sum_{i=0}^N ...

**16**

votes

**1**answer

1k views

### Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...

**0**

votes

**0**answers

150 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the ...

**6**

votes

**1**answer

141 views

### Minimal degrees of structures

For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$.
Given a ...

**8**

votes

**2**answers

570 views

### Did Bishop, Heyting or Brouwer take partial functions seriously?

The partial μ-recursive functions which may or may not be provably total seem to have some direct relation to the initial motivations for intuitionistic mathematics. (Following Kronecker, one ...

**3**

votes

**1**answer

215 views

### Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...

**17**

votes

**1**answer

436 views

### Are compact topological $n$-manifolds recursively enumerable?

Earlier this year it was asked on MO, "Are there only countably many compact topological manifolds?" Thanks to Cheeger and Kister, the answer is yes. On the other hand, Manolescu recently debunked ...

**15**

votes

**2**answers

474 views

### Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...

**3**

votes

**2**answers

233 views

### Comparing really big numbers

Is there an intractability theorem that says that in any sufficiently rich system for defining really big numbers, there will be two numbers for which it's very, very, ... very difficult to decide ...

**5**

votes

**0**answers

146 views

### List of finitely presented groups with undecidable word problem

Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?
By "representative" I mean "avoiding obvious redundancy", i.e. examples ...

**2**

votes

**1**answer

222 views

### Effectively non-recursiveness of some sets

A set $A$ is completely productive if there exists a computable function $f$ such that for every $e$, $f(e)\in (A-W_e)\cup (W_e-A)$. A set is effectively non-recursive if it is r.e. and its ...

**4**

votes

**2**answers

160 views

### Does the notion of provably total function depend on the chosen representation?

A typical definition of "provably total function in a theory $T$" goes like this (paraphrased from Odifreddi, Classical Recursion Theory II):
A function $f : \mathbb{N}^n \to \mathbb{N}$ is ...

**5**

votes

**0**answers

238 views

### Rice-like Theorems

Let $\varphi$ be an acceptable programming system. Consider the set $S=\{x\in\mathbb{N}:\varphi_x=\varphi_{x+1}\}$. By using Rogers' Fixed Point Theorem (RFPT) it can be proved that $S$ is a ...

**9**

votes

**0**answers

226 views

### (A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see ...