Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).

learn more… | top users | synonyms (1)

79
votes
0answers
2k views

What properties of busy beaver numbers are computable?

The busy beaver function $\text{BB}(n)$ describes the maximum number of steps that an $n$-state Turing machine can execute before it halts (assuming it halts at all). It is not a computable function ...
11
votes
0answers
193 views

Reference on standard types

This question is about what I presume is a basic construction in type theory. The finite types are defined as follows: 0 is a finite type; if $\sigma, \tau$ are finite types, then so is ...
9
votes
0answers
170 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
9
votes
0answers
146 views

Elementary references on Robinson Arithmetic, Prim. Recursive fns etc.

I'm in the middle of revising my freely available and much-downloaded introductory notes Gödel Without (Too Many) Tears. (They are a sort of cut down version of part of my Gödel book, and I'm ...
7
votes
0answers
190 views

Fixed points in computability and logic

I asked this question on CS.SE, too: http://cstheory.stackexchange.com/questions/27322/fixed-points-in-computability-and-logic I would like to understand better the relation between fixed point ...
6
votes
0answers
56 views

Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter). I have ...
5
votes
0answers
128 views

Recursive and Primitive recursive functions

According to the book that I'm reading, we can define the $\mu-$recursive functions inductively, as follows: The constant, projection, and successor functions are all $\mu-$recursive. If $g_1, ...
5
votes
0answers
96 views

Path to categorical realizability theory

I'm trying to understand the sorts of things found on this page: http://ncatlab.org/nlab/show/realizability In particular, I want to read Oosten's Realizability: An Introduction to the Categorical ...
5
votes
0answers
253 views

How is the Kleene normal form theorem for $\Sigma^1_1$ relations proved in RCA0?

All of the following concerns Simpson's Subsystems of Second Order Arithmetic (2nd ed.). In the notes subsequent to lemmas VII.1.6 and VII.1.7 (pp. 245–246), Simpson remarks that both lemmas are ...
4
votes
0answers
102 views

Is it decidable whether the iterates of a polynomial map are bounded?

Let $f:\mathbb{Q}^n\to \mathbb{Q}^n$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
4
votes
0answers
77 views

Is the measure induced by the Mandelbrot set computable on rational rectangles?

Is there a computable function that, given a positive rational number $\epsilon$ and a rectangle with rational corners $A$ returns a number $f(A,\epsilon)$ such that $|\mu(A \cap ...
4
votes
0answers
411 views

algorithm for solving diagonal quadratic equations over real or complex numbers

I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle): For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
3
votes
0answers
39 views

Induction Can't Prove Complexity?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
3
votes
0answers
98 views

What does “Turing-complete” really mean?

People talk about various programming languages or computational models being "Turing-complete." But what does that technically mean? The technical definition is buried under tons of informal ...
3
votes
0answers
67 views

Do there exist a pair of 'orthogonal' non-halting Turing machines?

I'll explain what I mean by orthogonal, which is probably a poor choice of words on my part. Given two Turing machines $\lambda $ and $\tau$,and two inputs $i$ and $j$. lets say $\tau(i) \preceq ...
3
votes
0answers
139 views

Whats the connection between Turing machine and First order logic?

Today in my Computing class i came across the theorem which states that., If language $L$ and $\Sigma^*\setminus L$ are recursively enumerable then L is recursive (total turing machine). Which looks ...
3
votes
0answers
87 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
3
votes
0answers
136 views

Simplifying Relations in a Group

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that any simple commutator with repeated generator is trivial; for example, $[[x_2,[x_1,x_3]],x_3]=1$. As I have asked ...
3
votes
0answers
255 views

How to derive Church-Kleene ordinal

Crossing-out: (How does one prove the existence of Church-Kleene ordinal? Also, why is it labeled as $\omega_1^{CK}$? And why is it first ordinal not hyperarithmetical, and is the first admissible ...
2
votes
0answers
17 views

$F[t]$ has undecidable positive existential theory in the language $\{+, \cdot , 0, 1, t\}$

Consider the ring $F[t, t^{-1}]$ (the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$). Theorem 1. Assume that the characteristic of $F$ is zero. Then the existentia theory ...
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
2
votes
0answers
27 views

Decidability - Complexity

Can someone tell me where I can get some information about the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots ...
2
votes
0answers
33 views

Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
2
votes
0answers
58 views

Properties of Ackermann's function

I want to show the following properties of Ackermann's function: $A(x,y)>y$. $A(x,y+1)>A(x,y)$. If $y_2>y_1$, then $A(x,y_2)>A(x,y_1)$. $A(x+1, y) \geq A(x,y+1)$. $A(x,y)>x$. If ...
2
votes
0answers
40 views

Is the probabilitistic distribution of the digits in the Chaitin's constant computable?

The Chaitin constant can in principle be computed with exponential effort on each sucessive digit by brute forcing all programs of a given length and simply proving special theorems on each case that ...
2
votes
0answers
36 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
2
votes
0answers
30 views

Computability of determining whether an expression equals zero

Suppose we are given an expression composed of integers,$ +, *, -, /,$ elementary functions $(exp, sin, cos, tan)$ and their inverses (and for simplicity, assume each argument to these functions is in ...
2
votes
0answers
66 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
2
votes
0answers
40 views

Kleene normal form : elementary?

The Kleene normal form explains there are primitive recursive functions $T$ (a predicate indeed) and $U$ such that for any computable function $\phi_n$, and for any $x\in\mathbb N$ : ...
2
votes
0answers
118 views

$n^{\text{th}}$ digit of $\sqrt{2}$ decimal representation is primitive recursive function

An exercise from Maltsev's "Algorithms and recursive functions". Problem: Let $\sqrt{2} = a_0,a_1a_2\dots a_n\dots$ be the decimal representation of $\sqrt{2}$. Show that the function $f(n) = a_n$ ...
2
votes
0answers
90 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
2
votes
0answers
44 views

Decidability of a language

Let $C$ be a conjecture about natural numbers. Let $$S = \{n\in N: n > m \text{ where $m$ is the first number found for which $C$ is false} \} $$ Is $S$ decidable? If $C$ is true for all ...
2
votes
0answers
24 views

Computable models of ($\omega$, <) without computable isomorphism

I read somewhere that "it is easy" to construct a computable presentation for the model ($\omega$, <) so that any computable isomorphism between this construction and the usual presentation of ...
2
votes
0answers
33 views

Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
2
votes
0answers
43 views

Meaning of Biinterpretability.

I'm reading this paper: http://www.math.cornell.edu/~shore/papers/pdf/hyp9.pdf and I am struggling with the meaning of Biintereptability, to quote the paper A degree structure $D$ is ...
2
votes
0answers
33 views

Bijection of simple set

Let $X$ is simple set (http://en.wikipedia.org/wiki/Simple_set) $Z \subset X$ is infinite recursive set. $Y = X$ \ $Z$. How to prove that there is a computable bijection $f$ that $x \in X ...
2
votes
0answers
40 views

Clarification of the argument for the set of total recursive functions not being recursively enumerable?

I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of ...
2
votes
0answers
123 views

Ackermann function is not primitive recursive

The function of the Ackermann function is defined as $$ A_{0}(y)= y+1$$ $$ A_{x+1}(0)= A_{x}(1)$$ $$ A_{x+1}(y +1)= A_{x}(A_{x+1}(y))$$ I want to show that the function of ackermann is primitive ...
2
votes
0answers
75 views

Check that constructed recursive function proves that set is recursive.

Let $\forall\exists$-formula be any formula that looks like $\forall x_1...\forall x_m$$\exists y_1...\exists y_n \phi$, where $x_1...x_m, y_1...y_n$ - variables, $m,n \ge 0$ , $\phi$ - unquantified. ...
2
votes
0answers
72 views

Eager vs. lazy interpretation of recursive functions

One of the ways of defining the set of recursive functions is to define first a language $L$ by induction in the following way: $\mathsf{Z}^1 \in L$; $\mathsf{S}^1 \in L$; $\mathsf{P}^n_k \in L$ for ...
2
votes
0answers
56 views

Why is positional number system natural?

In the theory of computation, one mainly deals with maps $\Sigma^*\rightarrow\Sigma^*$. To discuss computation on other sets $X$ than $\Sigma^*$, one fixes a representation ...
2
votes
0answers
84 views

Acceptable numbering of partial computable functions required to be one variable?

Soare in a yet unpublished textbook (I happened to be in a class taught by one of his former graduate students where we were field-testing a rough draft of his new textbook) Computability Theory and ...
2
votes
0answers
85 views

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete

Prove that $\{(x,y): W_x\text{ and }W_y\text{ are recursively separable}\}$ is $\Sigma_3$-complete This is a question from Soare's Recursively Enumerable Sets and Degrees. I have little idea how ...
2
votes
0answers
152 views

How to show Simp. and Creat. are $\Sigma^0_2$-Hard

Let Simp={$e:W_e$ is simple} and Creat={$e:W_e$ is creative} I'm having troubles showing these sets are $\Sigma^0_2$-Hard, ie that any $\Sigma^0_2$ set can be many-one reduced to them. I've already ...
2
votes
0answers
116 views

Unsolvability Degree in Turing's Proof 1

I have read that there is some debate over the exact origin of the Halting argument, which begins with Kleene and Davis in the 1950s [Copeland 2004]. Motivated by this I want to clarify the Degree of ...
2
votes
0answers
116 views

constructive ordinal and $\Delta^1_1$ predicate

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 ...
2
votes
0answers
214 views

Further question on “uncountable” Turing Machine

Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
1
vote
0answers
59 views

Algorithm to answer existential questions - Reduction

Lemma 1. For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and ...
1
vote
0answers
12 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
1
vote
0answers
29 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...