Questions tagged [decidability]
The decidability tag has no usage guidance.
76 questions
0
votes
1
answer
70
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 ...
6
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 ...
3
votes
1
answer
361
views
Is the problem of checking whether the intersection of any two given CFL is CFL?
Is the following problem decidable. "Given 2 CFL, L1 and L2. Is L1 $\cap$ L2 a CFL?"
- 33
-1
votes
1
answer
48
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 ...
- 169
1
vote
1
answer
39
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
81
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
31
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
45
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 ...
1
vote
1
answer
67
views
Computation theory: decidability and Turing-recognition
I have this question which I have some difficulties with:
"Given: There is a non-deterministic Turing machine that quickly recognizes language C.
Question: Is C necessarily a decidable language? ...
- 141
1
vote
1
answer
55
views
Non-deterministic TM with an oracle to $R$
Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$.
I'd ...
- 364
0
votes
1
answer
68
views
Why get this P=NP? What I am doing wrong?
As we know, all NP problems are decidable because there is a NTM that can solve them in polynomial time. To my knowledge, any NTM is equivalent to a DTM. Thus, if NP problems can be decided by a NTM e....
- 21
3
votes
2
answers
83
views
Decidability of {M | M accepts some x in less than |x| steps}
Is this language decidable?
{M | M accepts some x in less than |x| steps}
It feels like it should be undecidable but I can't think of a good proof that isn't similar to that of Rice's theorem (which I ...
- 31
0
votes
1
answer
94
views
Is the following language decidable?
Please confirm if my understanding of the below question, and my answer is correct.
Is the following language decidable? Justify your answer.
$L = \{\langle M_1,M_2\rangle \mid L(M_1) \cup L(M_2) = \...
- 103
1
vote
1
answer
49
views
Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$
If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable.
Then we can construct a $PDA$ that accepts ...
- 11
0
votes
1
answer
56
views
Decide if some DFA is accepted
Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)}
Show Some(DFA) is decidable.
I produced the following answer and wanted to check if I am correct
T="On input ...
- 1
0
votes
1
answer
64
views
If a language L over a finite alphabet A has both a subset and superset that are Turing-recognizable, does this make L Turing-Recognizable too?
"Let A be a finite alphabet, and let L1 and L2 be two Turing-recognisable languages over A such that L1 is a proper subset of L2, i.e. L1 ⊂ L2 but L1 ≠ L2. Let a language L over the alphabet A ...
- 1
4
votes
1
answer
139
views
Is the Turing machine the only framework to analyse limits of computation?
In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
- 381
0
votes
0
answers
20
views
General rules to tell if a language is regular/CFL/decidable/recognizable
I've been looking online for quite some time for some 'general' rules on this.
for example, there's a 'rule' that claims that if a language is like $$L={w\in {a,b,c}^* : count_\alpha (w) =count_\beta (...
- 367
2
votes
1
answer
59
views
Reduction from $ALL$ to $DECIDE$
Let $DECIDE=${$<M> :\ M\ halts\ on \ all \ inputs$} and I wish to show its unrecognizable using a reduction from $ALL=${$<M> :L(M)=\Sigma ^* $}
using a deterministic turing machine $R$ ...
- 367
0
votes
1
answer
196
views
Mapping Reduction from HALT?
I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
- 1
2
votes
3
answers
88
views
can a model of computation with infinitely many states be nontrivially decidable?
i'm trying to make a game in which the player faces an infinite (finitely specified) series of enemies and has to specify a strategy that provably defeats all of them (ie defeats enemy n in finite ...
- 417
0
votes
2
answers
121
views
$L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }
Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like?
Intuitively, I would say it's undecidable: We cannot predict if a given TM ever ...
- 11
-2
votes
1
answer
80
views
Is the "intersection" of the special Halting Problem with a language always undecidable?
I'm exploring the decidability characteristics of a particular language formed by the intersection of two languages, specifically in the context of the Halting Problem. The languages are defined as ...
- 11
0
votes
1
answer
118
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
58
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
1
answer
922
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
37
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 ...
- 387
0
votes
1
answer
117
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 ...
- 90
0
votes
0
answers
33
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
456
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 ...
- 317
0
votes
1
answer
88
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
- 317
1
vote
1
answer
173
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 ...
- 317
1
vote
0
answers
57
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
590
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
51
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
75
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
55
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
99
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
76
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?
- 173
1
vote
1
answer
46
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
482
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{ ...
- 469
0
votes
1
answer
126
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
2
answers
406
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
190
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
486
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.
...
user42948
3
votes
1
answer
1k
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 $$\...
- 201
1
vote
0
answers
79
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 $$\...
- 201
0
votes
2
answers
3k
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 $$\...
- 201
2
votes
1
answer
380
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 ...
- 443