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

8
votes
1answer
189 views

Groups whose word problem can be solved in constant time

Given a finitely generated group $G$, define an encoding of $G$ to be a one-to-one function $\Phi:G\to \bigcup_n \{0,1\}^n$ that sends each group element to a unique finite word. For $a,b\in G$, ...
5
votes
2answers
356 views

Consistent sentences with no arithmetically definable models

I've seen a construction of a sentence of first order logic that is consistent, but has no models with underlying set $\mathbb{N}$ and recursive functions and relations. Do there also exist consistent ...
2
votes
1answer
253 views

Is every computable real primitively recursively computable?

Let $\mathbb{N}$ be the set of all positive integers and let $P(n),Q(n)$ be a pair of general recursive mappings of $\mathbb{N}$ into itself such that for all pairs $h,k$ of distinct positive integers,...
1
vote
0answers
97 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 ...
11
votes
1answer
422 views

An efficient isomorphism between finite fields

Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
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 \...
13
votes
1answer
367 views

Turing degree of finding independent formulas

In this Paper of D. Isaacson, it is proved that the true arithmetic($Th(\mathbb{N}$)) is the only $\omega$-consistent and complete extension of $Q$ (Robinson's arithmetic). This, together with the ...
2
votes
1answer
130 views

Model existence and consistency conditions for $\Pi_1^0$ oracles

Let a $\Pi_1^0$ sentence be a sentence asserting that some given Turing machine never halts at the empty input tape. Let Q1 be a (potentially consistently lying) oracle for deciding $\Pi_1^0$ ...
12
votes
2answers
271 views

Can noncomputable sets be distinguishable in $RCA_0$?

Say that a set $X\subseteq\omega$ is distinguishable if there is some Turing machine $\Phi_e$ which, when given two sets exactly one of which is $X$, can determine which set is $X$. Formally, $X$ is ...
3
votes
1answer
96 views

Relationship between computational undecidability and axiomatic undecidability

On surface, these seem two completely different class of problems. One class represent statements which can't be proved or disproved in an axiomatic theory. For example One can write down a ...
6
votes
1answer
377 views

Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
2
votes
2answers
204 views

Linear systems of equations with singular coefficient matrix [closed]

Consider a consistent system of linear equations $Ax=b$. Let's assume for simplicity that $A$ is square $n \times n$. We are looking for an effectively computable approximate solution $\hat{x}$ in the ...
2
votes
1answer
171 views

What is the extension of the truth-table degrees to Baire Space called?

Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table reducibility....
3
votes
0answers
42 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\...
11
votes
4answers
1k views

How fast can the base-bumping function in Goodstein's theorem grow?

In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy ...
1
vote
1answer
117 views

Computable function [closed]

Let $f(n)$ be $$ f(n)=\begin{cases} 1,&\small{\text{if there are digits 1 in the constant $\textit{e}$ $\textit{n}$ times in a row}}\\ 0,&\small{\text{otherwise.}}\\ \end{cases} $$ Is it true ...
10
votes
1answer
369 views

What Turing degree is this function?

Over at http://www.scottaaronson.com/blog/?p=2725#comment-1089004 we had a discussion of intermediate Turing degrees. The following function came up: Take Chaitin’s constant, and rearrange its ...
-3
votes
1answer
139 views

Turing and Many one reductions in computability versus complexity

What are some non-trivial (please exclude poly time definitional difference) differences between Turing versus Many-one reductions in computability theory and those that occur in complexity theory?
7
votes
2answers
722 views

Complexity of Turing Machine behavior

If one looks at the code for a Turing Machine (TM) with $q$ states and, let's say, $2$ symbols, they all look pretty much the same: A list of $5$-tuples: $$ < state, symbol{-}read, symbol{-}to{-}...
8
votes
1answer
291 views

How long does the slow inefficient algorithm for computing the product in classical Laver tables take?

Let $(A_{n},*)$ denote the $n$-th classical Laver table. Let $X_{n}$ be the set of all finite sequences of elements from $A_{n}$. Define a function $E_{n}:X_{n}\rightarrow X_{n}$ by letting $E_{n}((...
7
votes
2answers
382 views

Decidability of diophantine equation in a theory

Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows: Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether ...
4
votes
5answers
7k views

Prove a function is primitive recursive

Hey, I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I ...
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). ...
3
votes
1answer
181 views

Inverse Ackermann Function

The inverse Ackermann function is defined over the natural numbers as follows: ($[x]$ means that we round up x to the nearest integer, while $\log^*$ is the iterated log function discussed here: http:/...
15
votes
4answers
2k views

Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings. ...
7
votes
2answers
397 views

Difference between constructive Dedekind and Cauchy reals in computation

If the Axiom of Countable Choice (ACC) $$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)] $$ ...
6
votes
1answer
333 views

Current status of computable spectral theorem and interpretation of quantum mechanics

The spectral theorem states if $A$ is a Hermitian operator acting on an $n-$dimensional Hilbert space space $H$, and $\lambda_1, ... \lambda_m$ are $m \leq n$ distinct eigenvalues of $A$, then $$ H=\...
3
votes
3answers
177 views

Coproducts and “Error Conditions” in Math vs CS

First, some background: recently in learning more about functional programming I saw one use for coproducts that surprised me a little bit: A function $f: A \rightarrow B \coprod C$ may result when ...
4
votes
2answers
227 views

(non-)existence of the aperiodic monotile

The aperiodic monotile problem asks whether there exists a single tile that every tiling of the plane made with it results non-periodic. What is known about this problem? If this tile exists, how can ...
2
votes
0answers
122 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 ...
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$ ...
4
votes
1answer
103 views

Are these two definitions of arithmetical hierarchy of real numbers equivalent?

Zheng and Weihrauch (http://www-sst.informatik.tu-cottbus.de/~wwwti/zheng/publications/1999/mfcs99.pdf) define a real number $x$ to be $\Sigma_n$ if and only if there is a computable function $f:\...
12
votes
1answer
639 views

Continuous functions and 2-bushy trees

The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison. A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...
2
votes
1answer
519 views

Can Turing machines clarify mathematical, philosophical, and physical existence?

From Harvey Friedman's manuscript on "Order Invariant Relations and Incompleteness": DEFINITION 4.4. A $\Pi_1^0$ sentence is a sentence asserting that some given Turing machine never halts at the ...
6
votes
1answer
259 views

Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...
11
votes
1answer
304 views

Is ordinal arithmetic more complicated than classical arithmetic?

Consider the first-order language $\mathcal{L}_{\text{OA}}:=(+,\cdot,0,1)$; in this language, we can formulate statements of ordinal arithmetic. Clearly, the theory $T_{\text{OA}}$ of $(\text{On},+,\...
3
votes
1answer
166 views

Theories of arithmetic from recursively inseparable sets

Edit: all sets / theories considered below are supposed to be recursively enumerable, although I'd also be interested in any possible generalizations to non-enumerable theories. In the comments on ...
56
votes
8answers
6k views

Succinctly naming big numbers: ZFC versus Busy-Beaver

Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge: You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
28
votes
5answers
905 views

Does the exact pair phenomenon for partial orders occur in your area of mathematics?

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if ...
5
votes
1answer
169 views

Deciding isomorphism between structures which interpret in the pure set

I am interested in the following decision problem: Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$...
2
votes
2answers
525 views

Can we compute every definable number with knowledge of the halting problem?

Suppose we knew the answer to the halting problem, and the halting problem for this new system with the old halting problem solved. And so on. Would this allow us to compute every definable number?
6
votes
2answers
158 views

a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known. I need a variant. (For those in the know, I need a c-bar which is ...
5
votes
1answer
129 views

“Partial-computably isomorphic” sets

For $A,B \subseteq \mathbb{N}$, define $A\sim B$ when there exist partial computable functions $f,g\colon \mathbb{N}\rightharpoonup \mathbb{N}$ such that $f$ is defined at least on all of $A$ and $g$ ...
22
votes
8answers
2k views

Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough to express all functions, Ackermann function being probably the best known example. Now, in the logic courses (that I have had look at)...
16
votes
1answer
1k views

What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem. What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...
2
votes
2answers
274 views

Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...
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 ...
3
votes
1answer
226 views

Can we use this symbol? [closed]

We consider the ring $\mathbb{C}[e^{\lambda x} \mid \lambda \in \mathbb{C}]$ and the language $L=\{+, \cdot , \frac{d}{dx} , 0, 1\}$. The ring consists of elements of the form $$\sum_{i=0}^N \...
16
votes
1answer
1k views

Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
0
votes
0answers
150 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 (...