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

28
votes
0answers
973 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 ...
25
votes
0answers
706 views

On certain representations of algebraic numbers in terms of trigonometric functions

Let's say that a real number has a simple trigonometric representation, if it can be represented as a product of zero or more rational powers of positive integers and zero or more (positive or ...
15
votes
0answers
659 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 ...
14
votes
0answers
145 views

Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where Cells on the tape can hold arbitrary elements of $\mathcal{S}$. The ...
14
votes
0answers
600 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 ...
12
votes
0answers
330 views

The topos for forcing in computability theory

My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site." My ...
12
votes
0answers
343 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 ...
11
votes
0answers
393 views

Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that $x^3+y^...
11
votes
0answers
167 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
502 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 ...
10
votes
0answers
154 views

Can we find minimal-diameter metrics without computability?

A beautiful argument by Nabutovsky and Weinberger (see http://math.uchicago.edu/~shmuel/fractal.ps) shows that, if $M$ is any smooth compact manifold of dimension $\ge 5$, then the diameter functional ...
10
votes
0answers
342 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 ...
10
votes
0answers
354 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 ...
9
votes
0answers
229 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 http://www.math.harvard.edu/~...
9
votes
0answers
250 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 ...
9
votes
0answers
395 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 ...
7
votes
0answers
183 views

$\alpha$-minimal degrees for singular $\alpha$

An important question in $\alpha$-recursion theory is whether there is a minimal $\alpha$-degree at $\alpha=\aleph_\omega.$ Question 1. Who first introduced the above question, and where can I find ...
6
votes
0answers
107 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). ...
6
votes
0answers
241 views

The least admissible above a dominating real

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
6
votes
0answers
190 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
0answers
151 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 ...
5
votes
0answers
241 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 non-...
5
votes
0answers
70 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
117 views

Can non-computable real numbers be defined without making use of any notions from computability theory

I am not sure if this type of question is appropriate for "mathoverflow.net", but I will take the chance. Are there any examples of (well-known or interesting) problems in geometry which ask for the ...
4
votes
0answers
117 views

Undecidability of the existential theory

Do you know if I can find the proof that the existential theory of $\mathbb{Z}$ with the structure of addition , divisibility and the relation $(\exists s \in \mathbb{Z})m=np^s$ is undecidable, ...
4
votes
0answers
180 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
101 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
105 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 $M$....
4
votes
0answers
350 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
370 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
44 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 $h:\mathbb{Z}\to\...
3
votes
0answers
108 views

Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
3
votes
0answers
132 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;1,2,...
3
votes
0answers
96 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
171 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 $E$...
3
votes
0answers
109 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
150 views

Banach spaces: A ball being a subset of the interior of the union of two balls

Let $X$ be a separable reflexive Banach space and let $A$, $B_1$, and $B_2$ be three closed balls in $X$. Is there a `handy' necessary and sufficient condition for checking whether $A \subseteq (B_1 \...
2
votes
0answers
123 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 ...
2
votes
0answers
158 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
86 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 ...
2
votes
0answers
149 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
238 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 ...
1
vote
0answers
98 views

Efficient deterministic algorithms of factorizing

My question is about efficient deterministic algorithms of factorizing polynomials of degree $n$ over $\mathbb{F}_q$. Are there such algorithms that use poly$(n, \log q)$ bit operations? I know ...
1
vote
0answers
84 views

A reference for “Borel Sets and Circuit Complexity”

Is there any pdf version of M.Sipser's "Borel Sets and Circuit Complexity" or , since I am unable to get this paper, is there other reference closely related to theory in that paper?
1
vote
0answers
126 views

Analogue break down between complexity theory and computability theory

Motivated by my post, Is there a program for theory of incompleteness in NP, much of NP-completeness theory has been heavily influenced by computability theory for which we were successful in proving ...
1
vote
0answers
127 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 ...
0
votes
0answers
34 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$ ...
0
votes
0answers
104 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 ...
0
votes
0answers
152 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 (...
0
votes
0answers
86 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 ...