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

1
vote
1answer
109 views

Total conditional complexity

By $C(|)$ denote conditional complexity. By $CT(|)$ denote total conditional complexity. For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$ but $CT(x|y) \ge n $. ...
20
votes
0answers
828 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 ...
14
votes
0answers
251 views

Computability of Brauer groups

A friend of mine and I were talking about computable algebra, and this question came up. The answer may already be known, but I couldn't find it with Google: Suppose I have a countable field, $k$. ...
12
votes
0answers
287 views

Do all linear orders in this class have computable copies?

This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
12
votes
0answers
573 views

Minimal resources for Undecidability of First-Order Logic: the number of variables

It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
11
votes
0answers
145 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 ...
11
votes
0answers
518 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 ...
10
votes
0answers
467 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 ...
9
votes
0answers
272 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 ...
9
votes
0answers
276 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 ...
8
votes
0answers
193 views

Infinite time game of life

Today in a talk with a friend of mine I had an idea of extending cellular automatons to transfinite working time. I know it has already been considered, but, as far as I can tell, GoL extended to ...
8
votes
0answers
315 views

“Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
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 ...
4
votes
0answers
60 views

TCAs (total combinatory algebras) with oracles

Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?
4
votes
0answers
151 views

Recursively Pointed Sacks Forcing and Preserving $\omega_1$

Let $\mathbb{P}$ denote recursively pointed Sacks forcing. This is forcing with recursively pointed perfect trees ordered by inclusion. A tree $T \subseteq {}^{<\omega}2$ is recursively pointed if ...
4
votes
0answers
72 views

Upper bound on ranks of well-founded trees in $SKI\Omega$ calculus

All ideas explained below are due to A.P.Goucher, and defined here. First of all, $SKI\Omega$ calculus is an extension of standard SKI calculus, with additional type of combinator, called oracle ...
4
votes
0answers
86 views

Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in ...
4
votes
0answers
250 views

About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , ‎of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
4
votes
0answers
257 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
0answers
105 views

What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers $\sqrt{A}$ and the integer $A$

What is the relation between the length of period of simple continued fraction expansion of quadratic algebraic numbers and the integer As we know,$\sqrt{2} = [1;2,2,2,2,…]$; while $\sqrt{14}= ...
3
votes
0answers
90 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 ...
3
votes
0answers
148 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 ...
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 ...
2
votes
0answers
91 views

Comparing two non-deterministic Turing equivalents as basis for Logic, request for references

I am designing a logic, that is simpler than FOL + PA. And I like to know if there already exists something in this direction. First of all a non-deterministic Turing equivalent is defined by ...
2
votes
0answers
102 views

Equivalence of LOOP (primitive recursive functions) and of SRL (reversible transformations) programs

This is a question about the decidability of program equivalence. Primitive recursive functions correspond exactly to the functions that can be implemented on a specific register machine usually ...
2
votes
0answers
134 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 ...
2
votes
0answers
209 views

A polytime feasible subuniverse of the Effective Topos

The effective topos is a well known universe of sets suitable for abstract computability, as it is build "from the ground up" via the classical notion of realisability by Kleene. I have found a few ...
2
votes
0answers
184 views

Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed? More precisely, suppose that for any deterministic TM $M$ accepting $$ ...
1
vote
0answers
108 views

Graph theoretical representation of Wang Tile

We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution. However, is there a well established counter-part ...
1
vote
0answers
76 views

Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?

Background By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that $$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
1
vote
0answers
121 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 ...
0
votes
0answers
63 views

Counting path generating sentences in a specific formal language

Given a formal grammar of a language or an Turing machine of the language, can we count the path that generating sentences of the language? For example, we know that if the grammar is context-free ...
0
votes
0answers
72 views

Linkage between homotopy equivalence and identification of algorithms

I vaguely recall that someone says there is linkage between homotopy equivalence and identification of algorithms which may be isomorphic or morphism or something like that,the algorithm may be ...
0
votes
0answers
126 views

Basis of periodic tiling of Wang tile

Given a set of Wang tile, Given 3 periodic tiling: A, B, C We define 3 vector F[A], F[B], F[C] each vector correspond to the appearing frequency of each type of tiles in the tiling. Now, we ...
0
votes
0answers
104 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; ...