**14**

votes

**5**answers

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

**2**

votes

**0**answers

135 views

### Reference for original paper (but translated to English) of Matiyasevich's proof of Fibonacci relation being Diophantine?

Hello. I am a maths undergraduate. I am doing a project about history of mathematics. I am looking for the original solution to Hilbert's 10th problem, or at least the theorems that is accessible to ...

**11**

votes

**0**answers

148 views

### Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones

Background
I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...

**3**

votes

**2**answers

196 views

### Smallest base to reach partial recursive functions as a closure of unbound search

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.
Do we need the "whole" set ...

**24**

votes

**1**answer

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

**1**

vote

**1**answer

168 views

### Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

I failed to get an answer at http://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here.
In ...

**4**

votes

**2**answers

343 views

### A question about primitive recursive functions

I have a question about primitive recursive functions. Maybe it's trivial, if it is I will move it into math.stackexchange.
Is there a primitive recursive function $f$ which is a bijection of $N$ ...

**10**

votes

**2**answers

1k views

### Categories of recursive functions

I have a couple of conjectures on recursive functions, that I feel must have been proved or refuted by someone else, but I don't know where to look. In short:
1. The primitive recursive functions ...

**9**

votes

**2**answers

416 views

### Reverse mathematics below RCA

I'm sure this is a fairly basic question, but I can't seem to find a solid answer:
My primary question is: Is there a reasonably nice subsystem of second-order arithmetic corresponding essentially to ...

**22**

votes

**0**answers

843 views

### Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes:
"Another mathematical eternal return: Toward the end of his ...

**1**

vote

**1**answer

151 views

### Grzegorczyk-hierarchy, growth-rate and functions with finite image

Grzegorczyk-hierarchy divides primitive recursive functions in distinct classes with respect to their growth-rate. It seems that the higher we go the hierarchy, the more tools we have to define ...

**2**

votes

**3**answers

326 views

### Indices of r.e. sets

The last part of the paper Located Sets and Reverse Mathematics [Journal of Symbolic Logic 65 (1999), 1451–1480] by Giusto and Simpson involves a proof as follows:
Given $A$ an effectively ...

**3**

votes

**2**answers

174 views

### Disjoint sets of fixed points 2

Let $\phi$ be an acceptable programming system. For every recursive function $f$, let $(f)=\{x:\phi_x=\phi_{f(x)}\}$ the set of fixed points of $f$. Now, let $S$ be a set and suppose that there exist ...

**9**

votes

**1**answer

427 views

### New research on coding in reverse mathematics?

Coding is obviously a fundamental tool in reverse mathematics, and practitioners take care to both demonstrate the correctness of their coding mechanisms and point out their limitations. Harvey ...

**2**

votes

**2**answers

134 views

### Size-limited oracles

I am interested in complexity of algorithms which have access to the following peculiar sort of oracle:
Suppose that an invocation of an algorithm f with an input of size n has access to an oracle ...

**18**

votes

**1**answer

809 views

### Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were ...

**3**

votes

**1**answer

216 views

### $\Sigma_1^0-COH$?

In reverse mathematics, $COH$ is a statement that there is a cohesive set for any uniform array of sets. Here uniform array of sets means that there exists a set $B$ such that $x\in B_e ...

**3**

votes

**1**answer

158 views

### Complexity of winning strategies for open games (for open player)

If $G\subseteq\omega^{<\omega}$ is a computable clopen game, then $G$ has a winning strategy which is hyperarithmetic $(\Delta^1_1)$, by an inductive ranking process. The key observation here is ...

**4**

votes

**1**answer

109 views

### Computable images of differences of r.e. sets

Suppose f is a computable function from a recursively enumerable set U to the natural numbers and that L,K are r.e. subsets of U. Is f(L-K) a difference of r.e. subsets? The motivation comes from
...

**8**

votes

**1**answer

801 views

### Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?

Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...

**8**

votes

**1**answer

277 views

### Cohesive sets with degree below some non-high 1-generic degrees?

Terminology:
Cohesive sets: $A\subset \omega$, for each recursively enumerable set $W_e$, either $A\cap W_e$ is finite or $A\cap(\omega\setminus W_e)$ is finite.
Non-high degrees: Degree $a$ such ...

**6**

votes

**1**answer

233 views

### Disjoint sets of fixed points

Let $\phi$ be an acceptable programming system. For every recursive function $f$, let $(f)=\{x:\phi_x=\phi_{f(x)}\}$ the set of fixed points of $f$. Now, suppose that $f$ and $g$ are recursive ...

**0**

votes

**0**answers

106 views

### Recursive relation using successor function

What is the recursive relation for
H(m)=2^(m^2)
using successor function
recursive relation for multiplication:
mult(x,0)=0;
mult(x,S(y))=add(x,mult(x,y))
recursive relation for addition:
add(x,0)=x;
...

**9**

votes

**0**answers

282 views

### Automorphism group of the Turing degrees

It is conjectured that the automorphism group of the Turing degrees, $Aut(\mathcal{D})$, is trivial. However, to the best of my knowledge, the current state-of-the-art is that $Aut(\mathcal{D})$ is ...

**4**

votes

**1**answer

167 views

### When do substructures have computable copies?

Say that a class $\mathcal{C}$ of countable first-order structures in some finite signature has the effective substructure property if $\mathcal{C}$ is closed under isomorphism and whenever $A\in ...

**16**

votes

**1**answer

611 views

### Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...

**9**

votes

**1**answer

188 views

### Ensuring nonempty lightface Borel sets have elements via theories of second-order arithmetic

This question is an outgrowth of this MathSE question: http://math.stackexchange.com/questions/276068/members-of-lightface-borel-sets.
A Borel set $X\subseteq 2^\omega$ is a member of the smallest ...

**4**

votes

**1**answer

384 views

### Definition of HYP in $L_{\omega_1^{CK}}[a]$?

The structure $L_{\omega_1^{CK}}$ consists of only HYP sets (I believe) and HYP in this structure is the same as the actual hyperaritmetic sets. Now if I move to the structure $L_{\omega_1^{CK}}[a]$ ...

**6**

votes

**0**answers

168 views

### $\omega$-models of $\mathbf{\Sigma^1_1}-DC$ and $\mathbf{\Delta^1_1}-CA$

So what is needed to demonstrate something (say like $L_{\omega_1^{CK}}[a]$ is a $\omega$-models of $\mathbf{\Sigma^1_1}$-$DC$ or $\mathbf{\Delta^1_1}$-$CA$? It's not like I don't understand what the ...

**5**

votes

**1**answer

216 views

### Notion of independence of Turing degrees

I've been thinking for a while about different ways two Turing degrees might be "independent" of each other (from the point of view of computability theory). The simplest such notion would be to say ...

**3**

votes

**0**answers

91 views

### Weak classes of diophantine functions

From a well-known work(s) by Putnam, Davis, Robinson and Matiyasevich, we know that every partially recursive function is diophantine.
Now it seems a natural question to ask: can we say something ...

**6**

votes

**1**answer

275 views

### Status of the Isomorphism problem for automatic groups?

I only ask because I don't know how to look for the answer.

**3**

votes

**2**answers

99 views

### How would one characterize a PR-complete language?

The complexity class $PR$ is the set of all formal languages that can be decided by a primitive recursive function. Is there any language $l$ known to be complete for this class, i.e., for every ...

**3**

votes

**1**answer

194 views

### Various notions of Turing reduction for partial functions

If $f$ and $g$ are partial functions $\mathbb{N} \to \mathbb{N}$, define six preorder relations $f \preceq g$ as follows:
$f \mathop{\preceq_{\mathrm{S}}} g$ ("$f$ is strict/Sasso reducible to $g$") ...

**11**

votes

**0**answers

527 views

### Groups generated by 3 involutions

Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$\tau_{r_1(m_1),r_2(m_2)}$ be the ...

**3**

votes

**2**answers

317 views

### Recursively enumerable sets as range sets of functions in Grzegorczyk-hierarchy

It is well known that recursively enumerable sets can be defined (among many other equivalent alternatives) as the range sets of primitive recusive functions (except for the trivial case of the empty ...

**8**

votes

**1**answer

254 views

### The equality problem between conjugate group elements

The Novikov--Boone Theorem, which is perhaps the archetypal local unsolvability result in group theory, states existence of a finitely presented group whose word problem is recursively unsolvable. ...

**2**

votes

**2**answers

300 views

### Second-order undecidability

Hi,
The idea of undecidability in computability theory seems to be along the lines of:
There can't be an effective procedure, that decides all instances of input, but a single instance can still be ...

**2**

votes

**1**answer

290 views

### A question about recursively enumerable sets of rational numbers

Let (Q*,<) denote the ordered set in which the elements of Q* are just the positive rational numbers
less than 1 and "<" is the ordering relation of the ordered field (of all rational numbers) ...

**9**

votes

**0**answers

283 views

### Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...

**3**

votes

**0**answers

152 views

### Alternate proof of van de Wiele's theorem in E-recursion

Hello, all
I'm currently trying to understand $E$-recursion theory, which is a generalization of classical recursion theory to arbitrary sets. One of the difficulties I'm having with understanding ...

**4**

votes

**1**answer

662 views

### Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...

**2**

votes

**1**answer

159 views

### The set of $\Delta_1$ indices

Is the set of Godel numbers of $\Delta_1$ formulae itself $\Delta_1$ definable (i.e., computable)?

**5**

votes

**1**answer

203 views

### Companion of the pointclass of inductive sets

This question is about the notion of a companion for a Spector class, as defined in Moschovakis's book Elementary Induction on Abstract Structures.
I am interested in Spector classes on $\mathbb{R}$, ...

**8**

votes

**1**answer

415 views

### Fast-growing hierarchy and Turing machines

Is it possible to get an estimate of the size of a Turing machine computing $f_\alpha(n)$, for a given $\alpha$ (I am especialy interested in moderately large $\alpha$ like the ordinal of ...

**2**

votes

**2**answers

222 views

### Computability of finding roots in holomorphic functions.

Consider a holomorphic function $f: S \to \mathbb{C}$ where $S$ is a path connected open subset of $\mathbb{C}$ (not necessarily simply connected). Is it then possible to determine if $f$ contains a ...

**24**

votes

**1**answer

803 views

### Can a string's sophistication be defined in an unsophisticated way?

This question is about sophistication, a way of measuring the amount of "interesting, non-random information" in a binary string, which was proposed by Kolmogorov and others in the 1980s. I'll define ...

**13**

votes

**2**answers

507 views

### Minimal degree of polynomial vanishing on the variety of small degree.

My question is assume that we know that the degree of some irreducible variety is small does it possible to conclude that there exists polynomial of small degree vanishing on this variety.
Let us ...

**2**

votes

**1**answer

349 views

### Turing-Complete Cellular Automata and Sym(Z)

Does there exist a Turing complete, cellular automata with universe and alphabet $\mathbb{Z}$ such that the only allowable configurations are permutations of $\mathbb{Z}$? Formally, consider $\tau : ...

**1**

vote

**2**answers

278 views

### Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...