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)

1
vote
1answer
219 views

Ackermann function in terms of higher order recursion

Wikipedia provides a higher-order definition of Ackermann function. First it gives the normal recursive definition \begin{equation*} A(m,n)=\left\{ \begin{array}{ll} n+1 & \text{if $m=0$} \\ ...
1
vote
1answer
231 views

Representing Recursion and Primitive Recursion diagrammatically

I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
2
votes
1answer
76 views

Prove $B = \{ \varphi_n(n) | n \in \mathsf{K} \}$ to be recursive

The set $B$ is the range of universal function given the domain $\mathsf{K}$, where $\mathsf{K} = \{ n | \varphi_n(n) \textit{ halts} \}$. How can we prove such claim?
3
votes
1answer
165 views

Members of (lightface) Borel sets

I'm fairly certain this question has a very simple answer, and that I've learned it before; I just can't seem to remember it. Suppose I have a nonempty lightface Borel set $X\subseteq 2^\omega$. What ...
0
votes
1answer
66 views

On Cardinalities of $\mathcal{RE}$ and $\mathcal{P}(\mathbb{N})$

We denote $\mathcal{RE}$ as the universe set of recursively enumerable sets. A set is recursively enumerable iff its semi-charactersitic function is computable (one can write its semi-verifier). The ...
3
votes
3answers
191 views

Definition of computability of real numbers?

What exactly does it mean to say that a real number $x$ is computable? I can think of two reasonable definitions but I am not sure whether or not they are equivalent: 1) There is an algorithm which ...
114
votes
1answer
3k 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 ...
2
votes
1answer
83 views

Proof that an inverse of a possibly noncomputable function is possibly not decidable

I'm stuck with the following homework: Given an fixed function $f:\mathbb{N}\to\mathbb{N}$. $f$ is an arbitrary (possibly not computable, possibly partial) function. Show that the set $\{f(42)\}$ is ...
2
votes
2answers
868 views

Examples of Many-one reductions.

I'm trying to wrap my head around many-one reductions for an assignment in Mathematical Logic. The assignment is to show $A$ r.e $\Leftrightarrow$ $A\leq_m K$ where $K=\{x\in\mathbb{N}\ |\ x\in ...
1
vote
1answer
118 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
7
votes
2answers
522 views

What is the relationship between ZFC and Turing machine?

I did not learn Logic properly but so far I understand that proof systems can be viewed as a kind of machine. For proof system, ZFC seems to be the most powerful one that we use so far. Similarly, for ...
0
votes
1answer
46 views

Intuition for “identification” and “generalization” (computability theory)

I am trying to decipher page 68 of Hermes' book on computability theory. One paragraph I am having trouble with is Let $Q$ be an n-ary predicate ($n \geq 2$). Let $1 \leq i < k \leq n$. Then ...
11
votes
2answers
592 views

Good introductory books on primitive recursive functions

I wondered if anyone could recommend any good introductory books on primitive recursive functions. I'm currently working through a Number Theory and Mathematical Logic module, and I'm finding it ...
6
votes
2answers
224 views

Ordinals definable over $L_\kappa$

Suppose $\kappa$ is an uncountable cardinal, with $L_\kappa$ an admissible set (i.e. a model of Kripke–Platek set theory). Let $<_\gamma \subseteq \kappa \times \kappa$ denote a wellordering of ...
2
votes
1answer
40 views

Prove there exists a recursive language which no TM accepts in n steps.

There is a problem I can't solve: Assume n is an integer. Prove that there exists a recursive language such that there is no Turing Machine which accepts it and makes a maximum of n steps for every ...
1
vote
1answer
106 views

Proving uncomputability — Rice's theorem

I am trying to prove the uncomputability of the following function: Let $\varphi$ be a Gödel-numbering of the computable functions. Consider the following function: \begin{align*} f(x) = \left\{ ...
3
votes
2answers
221 views

Primitive recursive select from parameters

I'm looking forward function, that works like that $\mathbb{N}^{n+1} \rightarrow \mathbb N$: $f(y, x_1, x_2, \dots ,x_n)=x_y$ We use projection $\Pi^n_k$, but I need something with "dynamic" size ...
5
votes
2answers
293 views

Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
0
votes
2answers
107 views

Is the halting of a program that checks for duplicates in an infinite multiset decidable?

A program $P(\Sigma)$ takes input $\Sigma$, which is an nonempty multiset. Let $\Phi$ be an empty multiset. Take any element $\sigma$ from $\Sigma$. If $\sigma \in \Phi$, return true. Otherwise, ...
2
votes
1answer
121 views

IF a language L logspace reduces to SAT, does L

If a language L logspace reduces to SAT, does L also reduce to SAT in polynomial time?
1
vote
1answer
147 views

Show that K and complement to K are “1-reducible” to EQ={⟨x,y⟩|φx≃φy}

Where $K = \{x | φ_x(x) \downarrow\}$, $φ_x$ is a $\mu$-recursive function computing $M_x$, $M_x$ is Turing machine with Godel's number $x$. Set $A$ is "1-reducible" to set $B$ ($A \leq_1 B$) when ...
-1
votes
1answer
258 views

How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
1
vote
1answer
192 views

The set of Turing machines that recognize $\{00, 01\}$ is undecidable

$L =\big\{\langle T\rangle \mid T\text{ is a Turing machine that recognizes }\{00, 01\}\big\}$. Prove $L$ is undecidable. I am really having difficulties even understanding the reduction to use ...
1
vote
2answers
385 views

The symmetric difference of two recursive (recursively enumerable) sets is recursive (recursively enumerable)

I want to prove it, but don't know how... (I've tried to resolve complement by defining characteristic function like this: $\chi_{\bar A} = 1 - \chi_A$) Any ideas please? :-)
1
vote
1answer
462 views

Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, ...
1
vote
0answers
34 views

Is it really true that $K(x|y) = K(x,y) - K(y)$?

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements. The first is well established: the ...
2
votes
1answer
105 views

unary recursive language

I'm having trouble with this question: Given any language L is a subset of $\{0,1\}^*$, define the language $$\text{unary}(L) =\{0^{1x} | x \in L\}$$ The language $\text{unary}(L)$ is ...
2
votes
1answer
170 views

question about Gödel numbering

I have a question about Gödel numbering, it is trivial but I would like to know how can you know the length of an expression through its Gödel number. ¿? I think you can use a recursive function but ...
3
votes
1answer
148 views

Question about $\Sigma_n$-soundness

According to wikipedia (http://en.wikipedia.org/wiki/%CE%A9-consistent_theory#Definition): "$\Sigma_n$-soundness has the following computational interpretation: if the theory proves that a program C ...
1
vote
2answers
213 views

Question about computability of true/provable formulas

I would like to clarify some things related to the computability of the sets of all theorems and true formulas for the formal arithmetic. Consider the theory $T$ of formal arithmetic (the theory of ...
1
vote
2answers
219 views

I do not understand why the Turing computable sets of N are exactly the sets at level $\Delta_1^0$ of the arithmetical hierarchy

The reason I don't understand it is this. Take for example the twin primes conjecture, which is $\Pi_2^0$. The set of twin primes is computable right? (there is a Turing machine that enumerates all of ...
8
votes
2answers
427 views

Is there any generalization of the hyperarithmetical hierarchy using the analytical hierarchy to formulas belonging to third-order logic and above?

As I understand, hyperarithmetical sets are defined according to the analytical hierarchy, that is, second-order-logic formulas. There is a generalization of hyperarithmetic theory named α-recursion ...
4
votes
1answer
434 views

Is there a decidable theory in propositional logic whose consequences are not decidable?

I want to know if there is a decidable theory in propositional logic whose consequences are not decidable. If there is, can we have a constructive example or we can only prove the existence of it? ...
6
votes
1answer
126 views

Is every context free language equivalent to one whose grammar has only one non-terminal symbol?

A context free language is generated by a context free grammar, which can be expressed in the Backus-Naur form e.g. I believe that if we only allow one nonterminal symbol in the grammar, the resulting ...
1
vote
2answers
227 views

Solving an equation in modular arithmetic

Given $A, B, C$ positive integers, $B < C,$ I would like some thoughts about (possibly efficient) ways to find the smallest integer $X$, where $0 < X < C$, such that: $$A X + B \pmod{C - ...
2
votes
2answers
640 views

How to solve this recurrence relation: $T(n) = 4\cdot T(\sqrt{n}) + n$

I was trying to solve this recurrence $T(n) = 4T(\sqrt{n}) + n$. Here $n$ is a power of $2$. I had try to solve like this: So the question now is how deep the recursion tree is. Well, that is ...
0
votes
1answer
52 views

Is a statement concerning the future part of a decidable problem?

Let Did I ever get 100% in an exam? be a problem and the corresponding (characteristic) function $$\chi(x)=\begin{cases}1,& \text{if the statement can be answered with ...
3
votes
2answers
885 views

Primitive recursive definition of the “divisibility” relation

Let $$d(x,y)= \begin{cases} 1, &\text{if }x\text{ is divisible by }y \\ 0, &\text{otherwise.} \end{cases}$$ How can I define $d(x,y)$ in terms of just the basic primitive recursive functions ...
1
vote
2answers
63 views

What is this number $k$?

I'm reading A first Course on Logic, (Hedman). An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion ...
1
vote
1answer
1k views

Language that is recursively enumerable, but not recursive

I have a problem with this task: Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing ...
6
votes
1answer
140 views

Terminal Paths in Kleene's O

I'm stuck on a problem in Sack's Higher Recursion Theory (#2.4)- any hints are welcome. He defines Kleene's O in the usual way, and the corresponding order $<_O$. A path through O is a linearly ...
0
votes
1answer
73 views

Why must language $L$ be decideable?

I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, ...
0
votes
1answer
98 views

Why is not language $L=\{w_i \mid w_{2i} \notin M_i\}$ recursively enumerable?

Why is not language $$L=\{w_i \mid w_{2i} \notin M_i\}$$ recursively enumerable? I need to show that by diagonalization, but dont know how? Its quite obvious for $L=\{w_i \mid w_i \notin M_i\}$, but ...
8
votes
3answers
765 views

Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language. This seems to imply that one ...
18
votes
3answers
708 views

How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?

This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound: "... in the context of ordinary ...
6
votes
3answers
329 views

From lightface $\Sigma^1_1$ to boldface $\mathbf\Delta^1_1$

Fix some standard Polish space, e.g. Baire's space. It's a simple observation that every $\Delta^1_1$ is also $\mathbf\Delta^1_1$. It is the same observation that $\Sigma^1_1$ becomes ...
0
votes
1answer
51 views

Define the Complement of Factoring?

I just need some clarification as to what this terminology means in this situation. A decision problem for $FACTORING$ is as follows. INPUT: an integer $n$ and a integer $d$ QUESTION: does $n$ have a ...
2
votes
0answers
122 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 ...
-1
votes
1answer
165 views

Unbounded number of tapes of Turing Machine

Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the ...
3
votes
1answer
202 views

Limits of Computable sequences

Turing introduced the fact that the limit of a computable sequence is not necessarily computable, and the Specker sequence is a specific example of such a number (with supremum not computable). My ...