# 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
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, ...
779 views

### What is wrong with this naive approach to Hilbert's 10th problem?

Background: I have been studying some decidability results in number theory. In doing so, I have always assumed there was no need for me to study pedantic definitions of decidability using Turing ...
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 ...
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 ...
440 views

### Algebraic closed field theory is $\Sigma_1$ (hence decidable)

In Bruno Poizat's Model Theory I found the following proof of ACF's decidability: 1) ACF is $\Sigma_1$, i.e. the set of sentences which are proved by ACF is definable by a $\Sigma_1$ formula. 2) ...
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, ...
160 views

### Why is the set of all tautologies in propositional logic recursively enumerable?

I've just started reading an english edition of Gems of Theoretical Computer Science. On page 5 (or page 12 of the overall pdf), the author brings up the set of all tautologies in propositional logic ...
73 views

### Algorithm to decide the universality / functional completeness of a set of logic gates?

Given a set of logic gates $G$, let $F_G$ denote the set of all formulas composed of gates from $G$. We say that $G$ is "universal for computation" or "functionally complete" if it forms a basis for ...
105 views

### Example of incomplete, but decidable theory, and of complete and undecidable theory, question

On wikipedia it is written that Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all ...
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 ...
107 views

### Showing that Presburger arithmetic is decidable by deciding if $\mathbb N \models \varphi$, but does it give provability in the axioms?

Here Presburger arithemtic is given by a set of axioms over the signature with binary operation $+$ and two constants $0$ and $1$. Similarly in Presburgers original paper he gives the arithmetic in ...
138 views

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

### Large Cardinals and Diophantine Equations (Penelope Maddy)

Professor Penelope Maddy remarks without elaboration in her famous 'Believing the Axioms' essay that 'It should be mentioned that the Axiom of Inaccessibles also has a few extrinsic merits. It ...
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 ...
64 views

### Is any context-free grammar in Chomsky form with at most 2017 rules necessarily finite?

A task from one of the former tests: Is there any algorithm, which for all pairs of context-free grammars over $\lbrace a,b,c\rbrace$ in Chomsky form $G_1,G_2$ with at most $2017$ rules correctly ...
61 views

### Choosing axiom schemes for a logical theory

In a Hilbert system, there are many ways that we can choose axiom schemes. My question is: 1- How do we know that we have defined enough schemes? What would happen if I remove a scheme from the list? ...
158 views

### Decidability of regularity of context-free grammar

I've searched for a long time, but cannot find this. Maybe it's an open problem, but it seems not that hard. Let's say I have a context-free grammar, say in Chomsky normal form for definiteness. Is ...
145 views

### Explicit example and the continuum hypothesis

I know that the continuum hypothesis is not decidable, i.e. we can not prove it, nor disprove it. The question is, is it theoretically possible to find an explicit set $E\subset \mathbb R$ such that ...
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. ...
38 views

### Undecidability of: $|w \in L| \geq 1, L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$

Let $a_0, a_1 \in \mathbb{N} \setminus \{0\}$ and $L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$ . Let's assume problem $P$ that, language of Turing machine accepts at least one word from ...
88 views

### Do given Turing Machines M,N accepts equinumerous languages?

I was doing some exercises from computability and complexity and then I have stuck on this problem: What type of problem (decidable, semi-decidable, undecidable) is the problem (show it): Do given ...
60 views

### Proving decidability of $(\mathbb N, +)$ with Quantifier elimination and evaluating basic formulas

The original proof of the decidability of Presburger arithmetic goes by Quantifier elimination, for example noting that $$\exists x (\underbrace{x + \ldots + x}_{\alpha\mbox{ times}} + b = c )$$ is ...
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 ...
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 ...
73 views

### Turing machine - Reducible

Given that Membership Problem is known undecidable Membership Problem: "Given a Turing machine M and string w, does M accept input w?" Emptiness Problem: "Given a Turing machine M, is L(M) = ∅ ?" L(...
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 ...
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 ...
163 views

59 views

### A axiomatization of (full) Second Order Logic with a decidable proof system cannot be complete; is this true if we only require semi-decidability?

My understanding is that, unlike first order logic, no "effective" (sound, consistent) axiomatization of second order logic is complete; there will always be statements true in all models, but not ...
225 views

### Classify language as decidable, undecidable but recognisable or unrecognizable

I'm currently studying unrecognizable languages in Turing Machines and came across this problem L1 := {< M > | M is a TM and M accepts at least one string w in {0,1}* with more zeros than ones} I ...