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

24
votes
1answer
728 views

Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether ...
0
votes
1answer
207 views

Random infinite sequences

An Algorithm/Turing machine Produces a symbol from a finite alphabet, and continues doing so infinitely. Another algorithm gets a copy of this symbol, ...
3
votes
1answer
120 views

What is the Arithmetical complexity of determining whether a 2-ary computable predicate has exactly one infinite column

Let $W_e$ be the $e$th computably enumerable set in a standard enumeration. For $A\subseteq \omega$, let $A^{[i]}:=${ $ a : \langle a,i\rangle \in A$}. What is the arithmetical complexity of {$e : ...
2
votes
1answer
137 views

Question about undecidable consequences of Con, learnability and arithmetical complexity of logical consequence

Let$\:$ $T=\{\varphi \in \Pi_1: PA+Con(PA) \vdash \varphi\:\:and\:\: PA\nvdash \varphi \}$. $\:$By the facts presented here Are undecidable consequences of Con recursively enumerable? by Andreas ...
5
votes
1answer
491 views

What can be done with computability logic that previous logic systems can't?

I've been reading a lot about computability logic lately and I'm superficially aware that it unifies classical, intuitionistic and linear logics. What I'm seeking to know is: Can computability logic ...
3
votes
2answers
245 views

Computability complexity of the first-order theory of arithmetic?

Hello, It's well known that Kleene's O is $\Pi^1_1$-complete. Does the same thing go for the first-order theory of arithmetic? (I'm talking specifically without set quantifiers---the theory of ...
19
votes
3answers
2k views

Is deciding whether a Turing machine *provably* runs forever equivalent to the halting problem?

Assume for this question that ZF set theory is sound. Now consider the language "PROVELOOP," which consists of all descriptions of Turing machines M, for which there exists a ZF proof that M runs ...
15
votes
1answer
843 views

Lawvere's fixed point theorem and the Recursion Theorem

Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\implies ...
5
votes
1answer
293 views

Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...
5
votes
1answer
358 views

First order consequence of a combinatorial principle

(Base theory $RCA_0$)The principle says there exists a function g such that g dominates any X-recursive function for any X in the model. i.e. For any $f\le_T X$, $\exists b\in M$ such that ...
14
votes
5answers
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
0answers
137 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
0answers
152 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
2answers
199 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 ...
29
votes
2answers
905 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
1answer
171 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
2answers
356 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$ ...
11
votes
2answers
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
2answers
419 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
0answers
861 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
1answer
154 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
3answers
331 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
2answers
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
1answer
429 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
2answers
138 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
1answer
820 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
1answer
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
1answer
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
1answer
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
1answer
832 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
1answer
284 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
1answer
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
0answers
107 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
0answers
292 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
1answer
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
1answer
625 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
1answer
193 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
1answer
388 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
0answers
170 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
1answer
220 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
0answers
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
1answer
276 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
2answers
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
1answer
202 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
0answers
531 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
2answers
325 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
1answer
260 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
2answers
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
1answer
296 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
0answers
292 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 ...