Questions tagged [semi-decidability]

Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.

Filter by
Sorted by
Tagged with
0
votes
2answers
1k 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 ...
2
votes
1answer
8k views

Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be: decidable (recursive) or undecidable (nonrecursively enumerable) ...
0
votes
1answer
32 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
1k 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 ...
4
votes
2answers
2k 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 ...
4
votes
4answers
199 views

Is the set of programs that compute some function other than $h$ recursively enumerable?

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable? Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated ...
5
votes
2answers
83 views

Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is co-recursively ...
1
vote
1answer
197 views

Suppose $L_1, L_2, …, L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?

Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive ? I see that for $x \in \Sigma^*$, $x$ belongs to ...
1
vote
2answers
1k views

Function is recursive iff its graph is recursively enumerable

So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive ...
0
votes
0answers
56 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
106 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
26 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
811 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
3answers
318 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
69 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 ...
0
votes
0answers
53 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
1k 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 ...
0
votes
1answer
68 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
3k 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
57 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
66 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
469 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 ...
3
votes
2answers
498 views

The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they ...
0
votes
0answers
131 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
153 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
2k views

Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
2
votes
1answer
202 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
1k 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
245 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
1k 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
256 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 ...
5
votes
2answers
233 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
votes
2answers
138 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
3k 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 ...
1
vote
2answers
58 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
492 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 ...
4
votes
0answers
619 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 ...
30
votes
2answers
5k views

Why are the total functions not enumerable?

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i....
6
votes
2answers
553 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-...
1
vote
0answers
648 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 ...
3
votes
2answers
400 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
1k 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
5k 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
166 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 ...
3
votes
2answers
575 views

Is the language of TMs that decide some language Turing-recognizable?

Is the language $\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$ a Turing-recognizable language? I think it's not, as, even if I am able ...
1
vote
1answer
1k views

Proving that a language of Turing machine descriptions is/is not Turing recognizable

How to approach to solve this question and the likes of it? Let $L$ be the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd ...
0
votes
1answer
400 views

Is this language semidecidable?

I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following . If $L_1$ is ...
2
votes
1answer
140 views

How to show that the set of TMs that accept languages of size two is recognizable?

I know how to show $\overline{Lx}$ is unrecognizable. I know how to show Lx is undecidable. I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable. For ...
-2
votes
1answer
1k views

Is the set of TMs that accept exactly two strings (each) semi-(decidable)?

I have found this problem- let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , ...