Tagged Questions

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).

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 ...
195 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 ...
4k 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 ...
86 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 ...
902 views

43 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 ...
110 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\{ \...
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 ...
295 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, ...
108 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, ...
123 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?
149 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 ...
265 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 ...
200 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 here....
396 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? :-)
470 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, sotrue(P)...
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 ...
107 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 ...
179 views

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 ...
149 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 ...
228 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 ...
222 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 ...
453 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 ...
455 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? ...
127 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 ...
227 views

965 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 (...
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 ...
2k 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 ...
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 ...
73 views

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 ...
125 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 ...
176 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 ...
214 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 ...
530 views

Examples of partial functions outside recursive function theory?

My math background is very narrow. I've mostly read logic, recursive function theory, and set theory. In recursive function theory one studies partial functions on the set of natural numbers. Are ...
130 views

Showing a set of true sentences is recursive

Let's assume we are working in $(\mathbb{N}, +, \dot\ , 0,1)$. Let $T$ be a set of formulae that is closed under $\neg$ and such that the set of Godel numbers of formulae in $T$ is recursive. ...