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)

73
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
189 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
137 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
55 views

Comparing different relativizations in computability

Most, but not all, theorems in computability relativize. In principle, we should go through the original proof to check that a relativized version of a theorem holds. In practice, we often just wave ...
7
votes
0answers
176 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 ...
5
votes
0answers
112 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
93 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
240 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
98 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
73 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
382 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
57 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
119 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
83 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
132 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
244 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
25 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
45 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
39 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
25 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
61 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
36 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
101 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
88 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
43 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
32 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
36 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
117 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
74 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
69 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
55 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
79 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
84 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
111 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
113 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
211 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
23 views

Is the computable numbers equal to the set of all the limits of finite length algebraic expressions?

Let's call $C$ the set of computable real numbers and $L$ the set of all the (existing) limits of finite length algebraic expressions. By $L$ I mean the set of all converging limits $\lim_{x_1 \to ...
1
vote
0answers
49 views

Primitive recursivness of a function. How does the function work?

So, I need some help with an homework assignment. Firstly: understanding the following function: $h(x) = \prod_{m=0}^{f(x)} m*f(m)$ From my limited knowledge of the product of sequences my guess is ...
1
vote
0answers
31 views

Are all finite languages regular?

I've been thinking about this for a while and still cannot come up with a way to show that all finite languages are regular. I know that all finite languages consist of finite number of strings that ...
1
vote
0answers
23 views

Enumerating general recursive functions with a primitive recursive function

I am reading "Set Theory and the Continuum Hypothesis", a monograph by Paul Cohen. In the preliminary chapter, he gives a proof that not all recursively enumerable sets are recursive. He begins by ...
1
vote
0answers
39 views

Need clarification on recursive functions.

Given any function $f: \mathbb{N}_0 \rightarrow \mathbb{N}_0$ and a recursive $h:\mathbb{N}_0 \rightarrow \mathbb{N}_0$ , I know that to prove $h\circ f$ is recursive I only need to prove that $f$ is ...
1
vote
0answers
51 views

A computable set of sentences neither probable nor disprovable from $PA$

I need to prove that, given a computable binary tree $T$ whose paths are exactly the complete extensions of $PA$ (via some Gödel coding), there is a computable $X\subseteq\mathbb{N}$ such that for all ...
1
vote
0answers
64 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
0answers
45 views

Find a $w$ such that $wxy = xyy$

Let $n,m \in \mathbb{N} \cup \{*\}$ and define $$nm = \begin{cases} \varphi_n(m) &\mbox{if } \varphi_n(m) \mbox{ converges} \\ * & \mbox{otherwise, including } * \in \{n,m\} \end{cases}$$ ...
1
vote
0answers
26 views

Question about Computability

Q:Suppose $U(n,x)$ is Gödel Universal Function, show that there is $n$ such that $U(n,x)=n+x$ for all $x$ I did some proof but I am mot sure if I am right. Let's consider a computable binary function ...
1
vote
0answers
62 views

An algorithmic approach to constructing the real numbers

To specify a real number, we can describe a rule which, given any rational number, tells you whether it's Too Big or Too Small. The rule should be self-consistent, in the sense that if $a$ is Too Big ...