Questions tagged [decidability]

Use this tag for questions about the existence of an algorithm that can and will return a correct true or false value to a decision problem.

35 questions
51 views

Can we enumerate finite sequences which have no halting continuation?

Note: this is a cross-post from CS.SE, since I haven't gotten an answer there. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
52 views

Is there a semi-decidable statement equivalent to the Collatz-conjecture?

We cannot rule out that the Collatz-conjecture cannot be proven. But we also cannot rule out that it is false and we cannot prove this in the case the sequence diverges for some start-number. Is ...
42 views

Relation between the monadic and two-variable fragment of first order logic

My question is whether there are any inclusions or relations with respect to decidability between the monadic and two-variable fragment of classical first-order logic.
84 views

Is this language decidable or not?

$$L_1 = \{ w \# x \mid w, x \in \{0, 1\}^∗ \text{ and M_w visit all of non-final-states at least once for any x} \}$$ $M_w$ is the encoded turing machine. sorry, this is my first time asking ...
188 views

Classify as decidable, semi-decidable or not semi-decidable

I have the set {p|∃y : Dom(ϕp) ⊆ Dom(ϕy)} and have to classify it as decidable, semi-decidable or not semi-decidable. I made a research and I found: Semi-Decidable If I have a word w ∈ L then a p ...
25 views

Show that the decision problem for implication is solvable if and only if the decision problem for validity is solvable

Having trouble with the forward direction of this proof. I assume that the decision problem for implication is solvable, so that for any set of sentences $T$, I can arrive at a yes or no answer to ...
78 views

Difference of two decidable languages?

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their ...
205 views

Proving the decidability of a language

I'm having issues with the decidability concept of a language especially the proving parts. I haven't been able to grasp the concept behind the prove completely and i need some assistance for it. The ...
111 views

The elementary theory of finite commutative rings

I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...
48 views

Combinatorial Problems, Normal Systems

In Computability and Unsolvability (Martin Davis), we have theorem 1.9 on page 87. It states, for every normal system T, we can construct a normal system T', whose alphabet consists of two letters, ...
35 views

Why can't the sequent calculus for First-Order Classical Logic be used for proving decidability via Proof-search?

I understand that Turing reduced the halting problem to the satisfiability problem of first-order logic thus proving first-order logic undecidable. However, when thinking about the sequent calculus ...
96 views

126 views

Recursion Theorem prime number

How to prove using the recursion theorem that the turing machine M cannot decide if the binary number 1< M>w is prime ? Where is the code of machine M.
21 views

Is intuitionistic first-order logic with no function or relation symbols decidable?

Classical first-order logic with no function or relation symbols is decidable. If I'm not mistaken, this is essentially because any formula (with possible free variables) has truth value uniquely ...
31 views

Symbols of the language vs. Free variables

For some context: I'm currently taking a course of Formal Methods and Logics and there's a passage where we show that the monadic second order ($\text{MSO}$) theory of (possibly labelled) linear ...
28 views

Decidability context-sensitiv and context-free grammars

Show that it is unsolvable whether a given context-sensitive language is context fre. And, show that the emptiness problem is solvable for one-way nondeterministic stack automata. I don't know how ...
53 views

17 views

If a language is NOT partially decidable, is the complement not partially decidable?

I am trying to figure out if L is partially decidable or not partially decidable. Let L be {encode(x): x is a Turing machine that halts on input encode(x)}.
30 views

Decidability of $\forall\exists$ diophantine equations

By saying $\forall\exists$ diophantine equations I mean sentences of the form: $\forall x\exists y\,[p(x,y) = 0]$ where $p$ is a polynomial on $x,y$, and both $x,y$ range over natural numbers. I want ...
73 views

Halting problem proofs and reduction

Okay so Ive got a problem with the "direction" of reduction and untimately the whole proof, reduction idea as a whole... My Question is: Prove that the problem of deciding whether a Turing Machine ...
20 views

$L_1= \{\langle M\rangle \mid$ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ Is $L_1$ RE or not RE?

I tried to prove $L_1$ is not Recursively enumerable via Rice's theorem, however i've been told by a mentor that examples i used are not valid. Can someone point out the mistakes in my understanding? ...
130 views

Application of Rice's Theorem

How can I prove, by applying Rice's theorem, that the language L is undecidable? $L = \lbrace \alpha : M_{\alpha}(x) =x^2 \,\,\, \forall x \in \lbrace 0,1\rbrace^* \rbrace$ I think this is a ...
Proving $E_{DFA}$ decidability by running $A_{DFA}$ a finite number of times(very tricky)
I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can i just use ...