Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
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 (...
1
vote
1answer
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 ...
1
vote
1answer
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.
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
6
votes
0answers
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 ...
4
votes
0answers
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, ...
3
votes
0answers
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 ...
3
votes
0answers
96 views

Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic

I am struggling with the following two problems: Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas $\{\varphi$ $\mid$ for every $M$-assignment $\...
3
votes
0answers
35 views

Deciding wether a language is regular, in the arithmetic hierarchy

I'm interested in the following problem REG_TM: given a Turing machine, decide whether its language is a regular one. Of course REG_TM is undecidable (via Rice or direct reduction), but I just read ...
2
votes
0answers
52 views

Can the question whether $x^a+y^b+z^c=n$ has a solution over the integers be undecidable?

Suppose, $a,b,c \ge 1$ are integers. Can the question whether the equation $$x^a+y^b+z^c=n$$ has a solution in integers $x,y,z$ for some particular integer $n$ be undecidable ? I ask because I ...
2
votes
0answers
64 views

Decidability/undecidability of the feasibility of optimization problems

I am building on top of this question on MathOverflow. The conclusion was that feasibility is decidable. Can one give a direct proof without using heavy machinery like Tarski's theorem? I do not ...
2
votes
0answers
68 views

Literature about decidable and undecidable theories

Is there some modern overview paper about decidable and undecidable theories? Something like Ershov's Elementary Theories or Tarski's Undecidable Theories. Particularly I am interested in result about ...
2
votes
0answers
33 views

SAT preserving conversion of statement to existential one

For me, a formula $\psi$ is existential if and only if it is of the form $\psi=\exists x_1\cdots\exists x_n \varphi$ such that $\varphi$ has no quantifiers. Prove or Disprove: There exists an ...
2
votes
0answers
163 views

Prime number decidability: recursion theorem

I have a problem with this task: Is there a Turing machine $M$ able to write the following language, where a $\langle M \rangle$ is the usual encoding of the machine $M$? The language is: $L = \{ w \...
2
votes
0answers
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.
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
53 views

Converting formula to a closed form with only existential quantifiers

Let there be some formula $\phi$, is there an algorithm to construct a closed formula $\phi'=\exists x_1...\exists x_n \psi$ where $\psi$ does not have any quantifiers and $\phi$ is satiable iff $\phi'...
1
vote
0answers
154 views

Prove that this language is decidable or not

L = {w#x| w,x ∈ {0, 1}$^*$ and $M_w$ have $BIN^{-1}$(x) different States} $M_w$ is the encoded Turing machine. It is definitely decidable, but i need to show a proof for that. I thought, that i can ...
1
vote
0answers
179 views

Which “natural” problems are independent of ZFC?

This question extends What are some natural arithmetical statements independent of ZFC? beyond the realm of just number theory. Scott Aaronson has pointed out that it's surprising how rarely the "...
1
vote
0answers
37 views

Is the solveability of a diophantine equation in two variables decideable?

Here : https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem it is stated that Hilbert's tenth problem is already undecideable, if we allow $9$ unknowns. I wonder whether the case of two ...
0
votes
0answers
24 views

does the language 𝐿 = {< 𝑀1 >, < 𝑀2 >: 𝐿(𝑀1 ) ⊆ 𝐿(𝑀2)} is in co-RE?

i was asked to determine if its in RE and if its in co-RE. well i think its easy to say the language is not in RE but i was wondering if this language is in co-RE. so the question is if $\overline{L}$...
0
votes
0answers
23 views

Decidability of a relation on Functional space!

Suppose I have this functional space $(D=\{ a\searrow b; a \in A , b \in B\}, \leqslant)$ (partial order relation on step functions!),also suppose that relation $\leqslant_1$ is decidable on $(A,\...
0
votes
0answers
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)}.
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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? ...
0
votes
0answers
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 ...
0
votes
0answers
61 views

Is the set {p | Lp is context free} decidable, semidecidable, or not semidecidable?

I have done some research and I know that it can be proven that every CFL is decidable (for example: https://pdfs.semanticscholar.org/f719/739f07c24c3790b63f3274037522b0b831c8.pdf). This means that we ...
-1
votes
0answers
22 views

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 ...