Questions tagged [semi-decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
158 views

Semi decidability proof

I'm studying for my theory of computation exam and came accross the following question: Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:...
7
votes
1answer
3k views

Why is the halting problem semi-decidable?

This is what is know about halting problem and semi-decidability :- Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x. A ...
1
vote
1answer
137 views

Unrecognizable languages relationship to NP-hard languages

I would like to know if there exists an NP-hard language which is also a member of co-RE\R? I think it depends if P=NP or not, but i'm not sure. Can I simply assume NP-hard is in R? Can you direct ...
0
votes
1answer
457 views

Is it decidable whether a Turing Machine will visit every non-end state from input x?

L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once} I believe this problem is undecidable. My proof would consist of me reducing L to a Halting ...
2
votes
1answer
326 views

Deciding on decidability of a problem and reducing it to halting problem if not decidable

Given are two following languages: $L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$ $L_2 = ...
1
vote
1answer
716 views

which of the following languages are Recursively Enumerable?

Which of the following languages are recursively enumerable? A={⟨M⟩∣ TM M accepts at most 2 distinct inputs} B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} For first language I think that we can ...
1
vote
1answer
98 views

Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $

Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer. $$L=\left\{ \...
0
votes
0answers
112 views

Why is $L=\{\langle M \rangle \mid |L(M)| \geq k\}$ not recognizable?

Here $M$ denotes a turing machine. By set theory, $L = \overline{E_{TM}} \cap \overline{L_0} \cap \overline{L_1}$ where $L_i=\{\langle M \rangle \mid |L(M)|=i\}$. And I know that $\overline{E_{TM}}$ ...
2
votes
1answer
374 views

Are recursively enumerable languages closed under shuffle?

For languages $L_1, L_2$ over some alphabet $\Sigma$, we define $$ \textit{Shuffle}(L_1, L_2) = \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \...
0
votes
2answers
152 views

Show that RE is closed against right-quotient

I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it. Assume some alphabet $\Sigma$ and two languages $A, B \...
0
votes
1answer
233 views

cardinality of recursive/r.e/not r.e languages? [duplicate]

I was just looking into properties of languages and wondered about the cardinality of them are all recursive languages countable or can they also be uncountable (can u have a recursive language which ...
0
votes
2answers
506 views

How can I prove that there is a decidable language which is not in P?

Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$: It will only take a input which has a form of a ...
0
votes
1answer
22 views

Semidecidability/Decidability for strings seperated by a non alphabet symbol

I am trying to prove the following: Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that $L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case ...
1
vote
1answer
727 views

Which Turing machine problems are Decidable?

Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ? Given a natural number $N$, does $M_N$ starting with an empty ...
3
votes
1answer
117 views

Complexity of the language of all TMs $M$ such that $L(M)$ is decidable

Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?
0
votes
0answers
52 views

Is undecidability of TMs' properties a statistical statement?

We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-...
1
vote
1answer
98 views

Given language consisting Turing machines is decidable or not?

$$L=\{M\mid \text{there exist }x,y\in\Sigma^* \text{ s.t. }x \in L(M)\text{ and } y \notin L(M)\}\,.$$ I think it's not recursively enumerable because this language reduces to complement of the ...
0
votes
1answer
25 views

Showing an equivalent definition of $CO-RE$

Let $L_1$ be a language. I would like t prove that $L_1\in CO-RE$ if and only if exists a language $L_2$ s.t. $L_1=\{ u\,\, |\,\, \forall_{v\in\Sigma^*} : <u,v>\in L_2 \}$ and $L_2\in R$. I'm ...
3
votes
1answer
743 views

Partial recursive function with no total recursive extension

We define a partial recursive function $f:\{0,1\}^* \longrightarrow \{0,1\}^*$ to be semi-good if we can define a total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f$, such for ...
5
votes
2answers
459 views

Definition of an immune set

I'm reading a theorem about existence of a simple set. The definition of an immune set can be found from here A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ ...
0
votes
0answers
63 views

how to prove that the property 'doesn't halt for some input' is not semidecidable

I am taking a computer theory class and one of the exercises is to prove that the property "doesn't halt for some input" is not semidecidable. This property is the negation of the property "halts for ...
5
votes
3answers
166 views

Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

L = {M | M is a TM and there exists an input that the TM M accepts in less than 50 steps} I need to find a minimal class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that ...
0
votes
0answers
47 views

Decidability of $\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$

I need to classify the set $$\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$$ as decidable, semidecidable or not semidecidable. I don't know how to start. Any ideas? Dom (φp) it's ...
0
votes
1answer
753 views

Is the given language decidable for turing machine?

I am going through undecidability of TM and found this question $L=\left \{ \left \langle M \right \rangle |M\ is\ TM \ and \ number\ of\ strings\ in\ the\ language\ \ is\ prime\right \}$ I think it ...
4
votes
2answers
1k views

Is the Rice Theorem applicable for these problems?

I have 1 problem :--> L = { < M > | TM halts on no inputs } I have solved the above problems by reductions given in the book and even there are many links ...
0
votes
1answer
60 views

Does it matter for this function if the set we check membership of is finite?

I have the following problem. Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f_i(x)$ with $f_i$ the $i$th partially-recusive ...
3
votes
1answer
2k views

Dovetailing in Turing Machines?

I was going through TM here and encountered a term "Dovetailing". What is exactly the dovetailing in Turing Machines? Can anyone mind to provide a good explaination with some examples?
1
vote
1answer
48 views

Is the given language decidable?

L = { < M > | M is a turing machine and } Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language . Now, L(M) is ...
0
votes
1answer
58 views

Is the set of pairs of TMs at least one of which accepts the empty word semi-deciable?

L = { < M1,M2 > | M1,M2 are TM's and Ɛ ∈ L(M1) ∪ L(M2) } Where Ɛ = Epsilon I know that this language is undecidable, but why it is semidecidable too. What i have tried is => Using Rice's ...
1
vote
1answer
377 views

Is this language semi-decidable?

Let $M_w$ be the DTM encoded by the binary string $w$ and let $$L=\{w\#x\,|\,\text{all states are reached when running }M_w\text{ on }x\}.$$ I've already proved that this language is undecidable (the ...
0
votes
0answers
94 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
2
votes
2answers
137 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \...
2
votes
1answer
166 views

Decidability of equivalence problem with limit

I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable. If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = L(...
-1
votes
1answer
929 views

Does Every Recognizable language has a subset not Recognizable?

Does every Turing Recognizable language has a subset which is not turing recognizable? i can give some examples but can't prove in general
-1
votes
1answer
121 views

Proof that {(M,w) | M accepts a prefix of w} is RE

Can someone help me go over that the following language can be recognized by a Turing Machine? $$L = \{\langle M,w\rangle \mid M \text{ accepts a prefix of } w\}$$ We can construct a universal ...
3
votes
1answer
745 views

Is Post's correspondence problem recognizable?

I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to ...
2
votes
1answer
235 views

Showing undecidability

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...
-1
votes
2answers
103 views

Is the following language decidable, enumerable or non-enumerable?

$$L = \{\langle M_1 \rangle, \langle M_2 \rangle \mid \text{\(M_1\) and \(M_2\) are TMs and \(\forall X, M_1(X) = M_2(X)\)}\}$$ Is this language decidable, enumerable, or non-enumerable? And in ...
2
votes
2answers
2k views

The language of machines that accepts all palindromes is not Turing recognizable

I have this question: $L = \{\langle M \rangle | M$ is TM that accepts every palindrome over its alphabet $\}$ Proof that $L$ is not Turing-recognizable by showing reduction from other non ...
6
votes
1answer
2k views

Reduction from ATM to ATM-complement

Is there a reduction from ATM to ATM-complement? (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) I have been thinking about it too much and couldn't find the ...
5
votes
2answers
229 views

Is the set of TMs that does not reach most cells to the right computable?

Let $L_{NTF} = \{ \langle M \rangle \mid $ for every $x\in\Sigma^* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \}$. I would like to prove or disprove $L_{...
1
vote
2answers
50 views

How to argue about semi-decidability of a problem?

I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it. I know that if a problem $\mathcal{P}$ is semi-decidable, then we can build a ...
1
vote
2answers
369 views

Undecidable language and Turing Machines

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ...
3
votes
0answers
426 views

Is English Recursively enumerable? [closed]

The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ...
1
vote
0answers
463 views

Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
5
votes
2answers
325 views

A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?

There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-...
3
votes
2answers
307 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?...
4
votes
1answer
782 views

Mapping reducibility vs. Turing reducibility

Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A \le_{T} B$, then if $B$ is ...
2
votes
2answers
4k views

Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable? What I ...
2
votes
0answers
160 views

How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...