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

0
votes
0answers
103 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; ...
8
votes
0answers
264 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
164 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
571 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
183 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
379 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
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
1answer
211 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
89 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
270 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
96 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
181 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
512 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
292 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
249 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
292 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
262 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
270 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
0answers
147 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
1answer
545 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
1answer
157 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
1answer
202 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
1answer
403 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
2answers
218 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
1answer
783 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
2answers
494 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
1answer
337 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
2answers
268 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 ...
3
votes
1answer
233 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
290 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
210 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
963 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
603 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
261 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
388 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
333 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 ...
19
votes
5answers
14k 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
504 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
94 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
275 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
876 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
240 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
613 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
447 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
486 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
582 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 ...
51
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
178 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$ ...