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

101 questions
174 views

### Tarski Undefinability examined under alternative basic assumptions [on hold]

I am taking this to be the generalized result of the Tarski Undefinability Theorem: All formal systems of greater expressive power than arithmetic necessarily have undecidable sentences. (The ...
41 views

### Decidability of Gödel sentences.

Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic. Gödel's first incompleteness theorem ...
61 views

### Prove that the following language is decidable / undecidable

Part A) Prove that the following language is decidable: Input: The description of a DFA A. Output: YES if A accepts the empty string. NO if A does not accept the empty string. I am struggling ...
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 ...
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 ...
20 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 ...
193 views

### What would be the effect on the Tarski Undefinability proof?

What would be the effect on the Tarski Undefinability proof: If his third equation was correctly decided to be false? 3) x ∉ Pr if and only if x ∈ Tr // page 275 Would the whole proof then fail ...
85 views

### Model Theoretical Interpretation of the Incompleteness of Number Theory

This question was sparked by this Numberphile video: https://www.youtube.com/watch?v=O4ndIDcDSGc. Near the end, (12:05), he speaks about the Riemann Hypothesis. He describes that if Riemann is shown ...
2k views

### How could Collatz conjecture possibly be undecidable?

I wonder how the Collatz conjecture could possibly be undecidable. Let's say it's undecidable, then no counter example can ever be found, and that to me seems to imply that none exist, and thus that ...
77 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 ...
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 ...
57 views

### Weakened versions of Word and Isomorphism Problems in group theory

Here are my questions: (Weakened Word Problem) Let $\langle X |R\rangle$ be a finite presentation of a group $G$, and let $w$ be an element of the free group $F(X)$. Does there exist an algorithm (...
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 ...
50 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 (...
13 views

### Specify a decisive Turing machine that calculates the following function $f$.

Specify a decisive Turing machine that calculates the following function $f$: \small f:\{a,b\}^*\to\{a,b\}^*\textrm{ with } f(w)= \begin{cases} (bba)^{3\cdot\#_b(w)}& \text{if } \#_a(w) \text{ ...
31 views

### Why does the unsolvability of the Halting Problem give a negative solution to the decision problem?

So Hilbert famously asked for a formalization of all of mathematics which was computationally decidable. Gödel is credited with shattering the idea that "all of mathematics" can be formalized. After ...
74 views

### The (un)decidability of the Tits Alternative for any given (suitably defined) set of groups.

Please forgive me if this question is ill-formed. I don't know much about decidability. Some Background: There are problems in combinatorial group theory that are undecidable, such as the word ...
35 views

### How Wang's conjecture implies decidability of The Domino Problem?

Wang stated following conjecture about Wang tiles (which was proven false by R. Berger): A finite set of plates [Wang's tiles] is solvable if and only if it has at least one periodic solution. ...
114 views

### Is determining derivability in propositional logic decidable?

I know that determining (semantic) entailment in propositional logic is decidable by the truth table method. For instance, let: $\phi = b \rightarrow a \\ \psi = b \lor c \rightarrow a$ Then we can ...
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}$...
55 views

### proof that specific disjoint sets are recursively enumerable, but don't lie in a decidable set and its complement

let's call a set $A \subseteq \mathbb{N}$ recursively enumerable if it's "partial characteristic function" $\tilde{\chi}_A$ is computable, whereby $\tilde{\chi}_A$ is defined as: $\tilde{\chi}_A$:= 1, ...
23 views

827 views

### Gödel's completeness theorem and the undecidability of first-order logic

I'm working through this module, "Undecidability of First-Order Logic" and would love to talk about the two exercises given immediately after the statement of Godel's completeness theorem. First, ...
96 views

75 views

81 views

### Does double negation elimination hold for decidable formulae in intuitionistic logic?

Let $P$ be a quantifier-free decidable formula, i.e. one can prove $P \lor \lnot P$. Does it follow that $\lnot \lnot P \to P$ intuitionistically? Informally, a decidability of a formula means ...
37 views

### Decidability if a given expression is equal to a prime number

Let us assume there is a number which is well-defined and computable, but it is hard to compute it. E.g., $x=\pi^{(\pi^{(\pi^\pi)})}$. It is not even known if the given number is an integer (which is ...