Questions tagged [decidability]
A set or language is decidable if its characteristic function is can be computed by an effective method. Use this tag when your question involves the (un-)decidability of a set or language.
82 questions
0
votes
1
answer
62
views
Prove that disjointlang := {⟨T , T ′⟩ : L(T ) ∩ L(T ′) = ∅}; is not decidable
Prove that disjointlang := {⟨T , T ′⟩ : L(T ) ∩ L(T ′) = ∅} is not decidable. I was thinking about reducing the problem to some other problem, but I'm not sure which and how.
0
votes
0
answers
70
views
Is it decidable whether a Turing machine modifies the tape or moves left a specific number of times on a given input?
I'm trying to understand whether the following languages are decidable or undecidable, and why. I would appreciate a clear explanation of the reasoning process, especially regarding how a machine's ...
- 181
3
votes
1
answer
79
views
Is the language L = { <M> | L(M) = L' } always undecidable when L' ≠ ∅?
Let $L' \subseteq \Sigma^*$ be a fixed, non-empty language.
Define the language:
$$
L = \left\{ \langle M \rangle \;\middle|\; L(M) = L' \right\}
$$
That is, $L$ contains the descriptions of Turing ...
- 181
0
votes
0
answers
56
views
Proof that set of all TMs that accept $ \epsilon $ is undecidable
I know how to write a proof for this problem using reduction from $ Halt_{TM} $, which is the same as the proof for Rice's Theorem but with a few minor adjustments. However, I am struggling with ...
- 103
0
votes
1
answer
126
views
Undecidable? Redundant computation detection
In a typical implementation of a Turing-complete procedural programming language, it's often desirable to detect redundant computations and optimize them away. But given that I can only think of ...
- 448
0
votes
2
answers
135
views
Why are finite sets decidable?
I am currently trying to understand why some finite sets or problems are always decidable.
For example, the halting problem on an empty tape is proven to be undecidable:
$$H_0 = \{w \in \{0,1\}^* \mid ...
- 55
1
vote
1
answer
173
views
Undecidability problem by Rice Theorem
I am studying complexity theory and I have problem with understanding some concepts about it. Can anyone help me please?
I have some problems with Rice Theorem. It says let $C$ be a class of partially ...
- 39
0
votes
1
answer
147
views
How to proof the existence of languages over {0,1}* that are neither semi-decidable nor co-semi-decidable
I am currently working on an assignment, and we have to prove the existence of languages over the alphabet {0,1} that are neither semi-decidable nor co-semi-decidable.
My intuition is that this can be ...
- 55
5
votes
3
answers
1k
views
Is partial correctness decidable?
Is partial correctness decidable? i.e., is there a general algorithm that for any pair of formal specification and encoded TM, returns true if and only if, when the TM halts, it meets the ...
4
votes
1
answer
403
views
Is the problem of checking whether the intersection of any two given CFL is CFL?
Is the following problem decidable. "Given 2 CFL, $L_1$ and $L_2$. Is $L_1 \cap L_2$ a CFL?"
CFL is an abbreviation for "Context Free Language".
- 43
-1
votes
1
answer
71
views
Deducing if a language is in $R \setminus P, P$ or $\notin R$
Let $A \in P$, and some language $B$. We have $f:\{0,1\}^{*}\to\{0,1\}^{*}$ s.t $\forall x \in \{0,1\}^{*}$ we have: $x \in B \iff f(x) \in A$.
In addition we know that there exists a family of cycles ...
- 189
1
vote
1
answer
67
views
Can a oracle TM for a language in $\Delta^0_{n+1}$ use two oracles for languages in $\Sigma^0_{n}$?
For reference, I am using Kozen's Automata and Computability, Lecture J. I am trying to prove that $\Delta^0_n = \Sigma^0_n \cap \Pi^0_n$.
In this book, I understood that Kozen defines $\Delta^0_{n+1}$...
1
vote
1
answer
117
views
Turing's Argument For Unsolvable Problems
At the heart of Turing's article for the Science News about solvable and unsolvable problems there is argument that he uses to show that there is no systematic way to decide whether a particular type ...
- 113
0
votes
1
answer
64
views
Decidability of Turing Machine
The problem is:
Argue, whether it is decidable if a Turing machine M halts within 10 steps on any input.
The proposed solution:
Simulate every input of length less than or equal to 10 on M. If M ...
2
votes
0
answers
60
views
Undecidability of a language similar to the Halting Problem
I would like to prove the undecidability of the following language $L$, closely related to the Halting problem: $$L:=\{w \mid M_w \text{ accepts a word of size }|w|\}.$$
It is obvious for unary ...