Questions tagged [decidability]
The decidability tag has no usage guidance.
56
questions
0
votes
1
answer
48
views
A program that solves the Halting Problem for programs with N states
My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
0
votes
2
answers
52
views
Why there can't be two instances of a "reverse" program in the Halting problem?
So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is ...
- 101
5
votes
7
answers
3k
views
What are the conditions necessary for a programming language to have no undefined behavior?
For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
0
votes
0
answers
22
views
Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape
I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct:
Let H0 be the ...
- 1
0
votes
1
answer
468
views
TMs can decide whether or not a string is a Palindrome, yet, the language called PALINDROMES is undecidable - why?
I came across this language, where M denotes a Turing Machine:
PALINDROMES $:= \{M \mid M \text{ accepts strings which are palindromes}\}.$ It is proven to undecidable.
And, I know one can construct a ...
1
vote
0
answers
35
views
How much is decidability compromised within this restriction of the fixpoint combinator?
Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang.
I considered this to be undesirable, and ...
- 335
0
votes
0
answers
23
views
Question regarding rice theorem
this is a question I got from a test that we had before
Let there be X, a subgroup of languages above $\Sigma $ such that X isn't empty nor all of the langauges in $\Sigma $ we need to say if the ...
0
votes
0
answers
23
views
Proving a language is recursively enumerable
Prove that the following language is recursively enumerable:
L = {<M,x> | Turing machine M enters the same configuration twice on input x}
I have tried to construct a TM that maintains the ...
- 23
0
votes
0
answers
28
views
How can decidability/semi-decidability/undecidability have impact on REAL life applications/examples?
How decidability/semi-decidability/undecidability has impact on REAL life applications/examples? I understand that it can be used for implementation of various algorithms but what else?
- 141
0
votes
1
answer
179
views
If a language is undecidable, then its complementary language must also be undecidable?
Reference from here If a Language is Non-Recognizable then what about its complement?
There exist complementary languages of unrecognizable languages that are recognizable, and there exist ...
- 305
0
votes
1
answer
46
views
Unrecognizable languages must be undecidable?
A decidable language must be recognizable.
Unrecognizable languages must be undecidable?
I want to know more about the relation of undecidability and unrecognizability
- 305
0
votes
1
answer
127
views
L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?
If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects
However, my question is that
If $L$ is a ...
- 305
1
vote
0
answers
52
views
Turing-reducibility for guaranteed decider
The following exercise is taken from Theoretical Computer Science by Atiba.
Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
- 11
0
votes
1
answer
253
views
Is the infinite union of decidable languages decidable?
I am currently struggling with figuring out the following problem:
Given decidable languages L1, L2, L3, L4, ...
Is the infinite union of Languages L1, ...... decidable? I have an intution that it is ...
- 103
-1
votes
1
answer
42
views
Prove that $L = \{ \langle M \rangle | \text{ M is a PDA, L(M) contains at least 1 string w that } |w| \leq n \}$ is recursive?
Description
Similar to the encoding of a Turing Machine, we can encode a Push-Down Automata. Denote $\langle M \rangle$ as the encoding of PDA M, and a natural number n, is language $L = \{ \langle M \...
- 3
0
votes
1
answer
61
views
Show that Lu is m-reducible to the language L = {⟨M, x⟩ | M(x) terminates with an empty tape}
Question: Given a language L, L = {⟨M, x⟩ | M(x) terminates with an empty tape}, show that Lu is m-reducible to L by finding a computable function f: Σ* -> Σ*, where for every w, w ∈ Lu if and only ...
- 1
1
vote
1
answer
51
views
Is it possible to determine if a 0-arity function [a program with no input] will always terminate
The halting problem concerns programs which take input.
By framing the halting problem on the diagonal argument it is clear why this is so.
What about programs with no input, constant functions.
Can ...
- 141
1
vote
1
answer
81
views
Is it computable to find the cardinality of intersection of two recursively enumerable sets?
I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is ...
- 121
0
votes
1
answer
72
views
Are there any formal systems or programming languages in which its only possible to define functions that have inverses?
Consider an algorithm $f(x)$.
Are there formal systems or programming languages that only allow $f(x)$ to be defined if $f^-1(x)$ exists?
- 165
1
vote
1
answer
34
views
If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?
I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable?
I think it is Undecidable since if ¬P holds then P ...
- 23
1
vote
1
answer
304
views
Language of Turing machines that go through some configuration infinitely many times on empty input
I've been going through some questions on old homework. Here was a question that confused me somehow.
Question: Given a language $$L=\{\langle M\rangle\ |\ M \text{ is a Turing machine. } M \text{ ...
- 453
0
votes
1
answer
116
views
Decidability of a context free Grammar
Say that a Context Free Grammar is red when it accepts every word of length 3 that begins with a, and extremely red when it accepts every word that begins with a.
Is redness decidable? or Semi ...
- 1
1
vote
1
answer
250
views
A decidable language that can't be decided by a circuit ensemble of linear size
Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
- 11
0
votes
0
answers
151
views
Prove that the problem of REGEX producing strings with 111 as substring is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given <...
- 17
1
vote
1
answer
378
views
For any two languages A and B there exists J such that both A and B are Turing reducible to J
Here is the my attempt:
Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings.
...
1
vote
0
answers
656
views
Prove that determining if a PDA has an infinite language is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 181
1
vote
0
answers
49
views
Prove that the problem of CFG producing epsylon is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 181
0
votes
2
answers
1k
views
Show that ALL DFA is decidable
I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser):
Given $$\...
- 181
2
votes
1
answer
252
views
A language of natural numbers is decidable iff it is either finite or the image of some strictly increasing computable function
Suppose $L \subseteq \mathbb N$ such that, for the purpose of Turing machine
computation, numbers in $L$ are represented by strings over the alphabet $\{0, 1\}$ in the
standard binary notation. Prove ...
- 423
1
vote
0
answers
49
views
Does description method matter in Rice’s theorem?
If $\mathcal{p}$ is a nontrivial property of formal languages, then
$L_{\mathcal{p}} = \{ \langle M \rangle \mid L(M) \in \mathcal{p} \}$ is undecidable by Rice’s theorem.
What if we describe ...
- 358
-2
votes
1
answer
42
views
Decision problem
Prove the following theorem
Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P.
Could anyone be able to prove it?
- 111
2
votes
1
answer
1k
views
Useless states in a PDA
I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads:
4.22 A useless state in a pushdown automaton is never entered on any input string. Consider the ...
- 123
0
votes
1
answer
25
views
Show that $ Y \subseteq A^*$ is decidable
Let A be a nonempty alphabet, $X ⊆ A^*$ a decidable set, and $Y ⊆ A^*$
be a semi-decidable set. We assume that $Y ⊆ X$ and that $X \setminus Y ⊆ A^*$ is semi-decidable. Show that then the set Y ⊆ A∗ ...
- 3
0
votes
0
answers
42
views
If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?
There is a lemma in our textbook that asks us to prove the following:
If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable
I tried proving this by saying that if $L_1 \leq_m L_2$, ...
- 29
0
votes
1
answer
44
views
Can 3-SAT be recognized in less than exponential time?
Obviously it is an open question if $3$-SAT can be decided in a polynomial amount of time. But what results do we know about its recognizabilty? Can $3$-SAT be recognized in a polynomial amount of ...
- 147
0
votes
0
answers
154
views
Decidability of the language of a regular expression being a subset of a given context free language
Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG.
Is it decidable that G accepts whatever the regular expression does? In other words, ...
- 11
0
votes
0
answers
71
views
Complement of a context free language
Consider the context-free language of balanced parentheses of three kinds:
$$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$
What will be the ...
- 3
1
vote
1
answer
185
views
Decidability for intersection of context free and regular languages
I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
- 13
-1
votes
1
answer
71
views
Does Turing machine move left on particular input?
We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check ...
- 346
0
votes
1
answer
224
views
Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?
Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-...
- 346
0
votes
0
answers
37
views
Why linear bounded automata emptiness and finiteness isn't decidable? [duplicate]
We know that linear bounded automata has tape size based on input size which is limited. Context-sensitive languages are accepted by LBA. My question is that if LBA has limited tape size why it's ...
- 346
0
votes
1
answer
290
views
Why REC languages is undecidable under emptiness and finiteness?
Membership problem of Recursive languages are decidable.
My approach:
Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it.
For string $w,$ if $w ∈ L,$ then $M$ halts in ...
- 346
0
votes
1
answer
212
views
Rice theorem could apply except RE language?
You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages.
$Q_1:$ So ...
- 346
0
votes
2
answers
573
views
Regularity of CFG and DCFL
I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.
My ...
- 346
0
votes
1
answer
214
views
Why finiteness problem of CFL is decidable?
We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?
- 346
0
votes
1
answer
102
views
Reduction from undecidability, decidability to decididabilty
If given any two language both
$L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
- 346
0
votes
0
answers
38
views
Is this language in RE?
Given the following language:
$$L=\left \{ <M> | \exists L \in R \quad s.t \quad L(M)\subseteq L \right \}$$
I need to determine it's compuation class(R or RE).
I used Rice Theorem as follows to ...
- 217
0
votes
0
answers
47
views
Loop in control flow graph of a program versus checking whether program goes into infinite loop or not
Which of these is true or false.
1)If Control Flow graph(CFG) doesn't contain any loop, the program will never go into infinite loop.
2)If CFG contains loop, the program may or may not go into ...
- 117
-1
votes
1
answer
55
views
How to determine whether this language is regular?
I've encountered this question recently: Given $\Sigma=\{\sigma_1, \sigma_2, ..., \sigma_n\}$ and $n\ge 2$, determine whether the following language is regular or not:
$$
L_1=\{w\in\Sigma^*|for \ 1 \...
- 1
0
votes
1
answer
50
views
Prove decidable
L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s }
T = "On input where M is encoded DFA"
...
- 15