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

18 views

### How do we show that $A$ is polynomial time reducible to itself? [duplicate]

How do we show that $A$ is polynomial time reducible to itself, i.e. that $A \le_p A$? I know how to prove that it is transitive, but I don't know how to prove it's reflexive. I'm aware that it's ...
27 views

### Reducing Pcp (Post's correspondence problem) to mPcp

Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version ...
68 views

29 views

### Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable?

Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable? My intuition tells me the answer should be no, but I can't prove it. I know that ...
21 views

### simple questions on $TM$s runs lengths

Is it possible that the number of running steps in $TM$ that runs on word $w$ will be $0$? Is it possible that the number of running steps in $TM$ that runs on the empty word $\epsilon$ will be bigger ...
447 views

### Approximate spectral decomposition

A detailed attempt below. I am interested in effective and constructive computations for finding approximate spectral decompositions in some suitable format. Namely, let $A: H \rightarrow H$ be a ...
78 views

### Faster growing function than the fast growing heiarchy under Church-Kleene?

Is there a computable function that grows faster than any function in a fast growing hierarchy with index less than the Church–Kleene ordinal, where computable fundamental sequences are used? If the ...
7 views

### Simulating a k state Turing machine M would require a Turing machine M' that has some f(k) number of states

I am writing a proof for a problem, and in that proof, I am simulating a TM M that has k states and terminates after being started on a blank input. I want to show that to simulate M on a TM M', M' ...
41 views

### Prove that a certain intrinsic property of Turing machines is not decidable

Can anyone help me to prove that the following language is nod decidable?  A=\{\langle\,M,w,q\,\rangle\mid M \text{ is a $TM$ , $w$ is a word, $q$ is a state in $M$ and while $M$ runs on $w$ it ...
53 views

### Multiplicity of real numbers in a tuple with known cardinality decidable?

Given a tuple $(x_1, \ldots, x_n)$ of computable real numbers $x_1, \ldots ,x_n$ and its cardinality $|\{x_1, \ldots x_n\}|=d \leq n$, is it decidable which numbers have which multiplicity? In other ...
42 views

### Classifying languages

I'm working on understanding what kind of languages are decidable, recognizable, and co-recognizable. I came across this problem that I think will really help me but I'm still quite unsure of how to ...
59 views

### Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
24 views

### decidable intersect undecidable

Hello I'm kind of having trouble with computability, so my question is I need to define af language A and B such that A is decidable and B is undecidable when I do $A\cap B$ is decidable. also ...
47 views

### Does this sketch proof that every formula is equivalent to one in the arithmetical hierarchy work?

In the lecture notes for my course, the arithmetical hierarchy is defined as follows: A formula is $\Sigma_0$ or $\Pi_0$ if every quantifier is bound; A formula is $\Sigma_{n+1}$ if it is of the ...
98 views

### Show that the following function is primitive recursive

Let $f$ be a function defined by \begin{array}{l} f(0)=1;\quad f(1)=2;\quad f(2)=3;\quad f(n)=0 \mbox{, for $n>2$} \end{array} How to show that $f$ is primitive recursive?
21 views

### Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
22 views

### Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
36 views

### proof that languages are/are not in RE (probably with mapping reduce)

Given $2$ languages: Let $u \in \Sigma^*$ (constant word). $A_u=\{<M> \big{|}\,\, u\in L(M) \text{ and M is TM }\}$ $B_u=\{<M> \big{|}\,\, L(M)=\{u\} \text{ and M is TM }\}$ I ...
37 views

### A semi-recursive infinite set is the range of some injective recursive total function

The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims: A set S of natural numbers is called recursively enumerable if there is a partial recursive ...
42 views

### Ramsey theorems for the naturals and for general infinite sets

In reverse mathematics and in recursion theory, the infinite Ramsey theorems are usually stated in terms of coloring of $[\Bbb N]^n$. How do these (not) imply the Ramsey theorems for general infinite ...
22 views

### turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
38 views

### turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...