Skip to main content

Questions tagged [decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Mikayla Eckel Cifrese's user avatar
4 votes
1 answer
126 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 ...
math boy's user avatar
  • 359
4 votes
1 answer
2k views

A language is Turing recognizable iff it is a projection of a decidable language

I was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to ...
Optimistic's user avatar
3 votes
1 answer
107 views

Effectively decidable vs. noneffectively (or ineffectively) decidable

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I ...
user avatar
3 votes
2 answers
73 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 ...
defonottyler's user avatar
3 votes
1 answer
957 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 $$\...
Stecco's user avatar
  • 201
2 votes
3 answers
71 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 ...
Silver's user avatar
  • 417
2 votes
1 answer
358 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 ...
SVMteamsTool's user avatar
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 ...
t42d's user avatar
  • 123
1 vote
1 answer
52 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 ...
RFV's user avatar
  • 141
1 vote
1 answer
414 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{ ...
Mohamad S.'s user avatar
1 vote
1 answer
426 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. ...
False Equivalence's user avatar
1 vote
1 answer
42 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 ...
Richie Harvy's user avatar
1 vote
2 answers
1k views

Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable. To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
Leon's user avatar
  • 41
1 vote
1 answer
162 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 ...
lz9866's user avatar
  • 315
1 vote
1 answer
92 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 ...
T. Rex's user avatar
  • 121
1 vote
1 answer
256 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 ...
markovv.sim's user avatar
1 vote
1 answer
78 views

Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
hermi's user avatar
  • 75
1 vote
1 answer
36 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 ...
Air Homely's user avatar
1 vote
1 answer
50 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$ ...
Aishgadol's user avatar
  • 355
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 ...
Dannyu NDos's user avatar
1 vote
0 answers
55 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 ...
jase's user avatar
  • 11
1 vote
2 answers
339 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 ...
user149788's user avatar
1 vote
0 answers
55 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 $$\...
Stecco's user avatar
  • 201
1 vote
0 answers
50 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 ...
Omid Yaghoubi's user avatar
1 vote
0 answers
92 views

The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can. First, here is an hypothesis: diagonalization is syatematically used to prove ...
Hugolin Bergier's user avatar
0 votes
1 answer
58 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....
Ali.A's user avatar
  • 11
0 votes
1 answer
380 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 ...
S. M.'s user avatar
  • 327
0 votes
2 answers
771 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 ...
S. M.'s user avatar
  • 327
0 votes
1 answer
74 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?
newlogic's user avatar
  • 165
0 votes
1 answer
302 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-...
S. M.'s user avatar
  • 327
0 votes
1 answer
57 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) = \...
Mike Q's user avatar
  • 103
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 ...
YKY's user avatar
  • 101
0 votes
1 answer
501 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 ...
Druckermann's user avatar
0 votes
1 answer
119 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 ...
kmvfkmfv's user avatar
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 ...
Craig's user avatar
  • 147
0 votes
1 answer
262 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?
S. M.'s user avatar
  • 327
0 votes
1 answer
59 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 ...
Mark's user avatar
  • 1
0 votes
1 answer
344 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 ...
lz9866's user avatar
  • 315
0 votes
1 answer
67 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
lz9866's user avatar
  • 315
0 votes
1 answer
68 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 ...
Jane's user avatar
  • 1
0 votes
1 answer
29 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∗ ...
Ouun's user avatar
  • 3
0 votes
1 answer
110 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 ...
S. M.'s user avatar
  • 327
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" ...
user260541's user avatar
0 votes
1 answer
39 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 ...
keth's user avatar
  • 1
0 votes
0 answers
18 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 (...
Aishgadol's user avatar
  • 355
0 votes
1 answer
114 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 ...
Diode's user avatar
  • 1
0 votes
2 answers
111 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 ...
Dilara's user avatar
  • 11
0 votes
1 answer
70 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. ...
Vincenzo Buselli's user avatar
0 votes
0 answers
24 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 ...
dport's user avatar
  • 1