Questions tagged [undecidability]

Questions about problems which cannot be solved by any Turing machine.

Filter by
Sorted by
Tagged with
1
vote
1answer
437 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
1answer
1k views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For $\...
1
vote
1answer
504 views

Recursive language with non-recursive subsets

I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question: Recursive language with non-recursive subsets. Does ...
1
vote
1answer
654 views

If a problem is “not semi-decidable” and “not decidable” can we say it is “undecidable”?

I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram. However, in my ...
1
vote
1answer
950 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
1
vote
1answer
2k views

Proving that DFA equivalence is decidable

The following question is taken from Sipser: Prove that $EQ_{\mathsf{DFA}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works. Here is the ...
0
votes
0answers
41 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
28 views

how is the set of undecidable programs related to the set of non-halting programs?

Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting? Thanks!
0
votes
0answers
324 views

Turing machine M overwrites a non-blank char by B (Blank)?

What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'? Intention of the question: I am trying to answer how the halting ...
0
votes
1answer
2k views

how do I find a undecidable subset of a set that's decidable? [closed]

Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
0
votes
1answer
100 views

Determining if a TM decidable or not, with limited information

Were being asked to determine the whether this Turing Machine is decidable or not "Given a two way, one-tape DTM $M$ whose tape set is $\Gamma=${$a,b,B$} and a string $x\in${$a,b$}*, determine ...
0
votes
0answers
143 views

Can we recognize wheter a Turing machine is a decider? [duplicate]

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-...
0
votes
0answers
68 views

Decidability of a given language

$L_1=\{ ⟨M⟩ ∣M$ takes at least 2016 steps on some input$\}$ the answer says $L_1$ is recursive. I am stuck at one point and i am wasting my time on it here for $L_1$ if we are given a set of to see ...
-2
votes
2answers
131 views

Why Rice theorem work for decidability?

Rice's theorem states: Every nontrivial property of recursively enumerable language is undecidable. I came across following problems, which Ullman's books say both are undecidable: Turing ...

1 2
3