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.

15
votes
2answers
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, ...
11
votes
1answer
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 ...
6
votes
3answers
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 ...
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
1answer
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) ...
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
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
138 views

Is completeness of a propositional axiom set decidable?

In propositional logic, given a set of logical connectives, axiom schemas and deduction rules, is it decidable whether the logic system is complete? Is it decidable for the special case of $\{\to, \...
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
2answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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? ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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. ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
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
1answer
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(...
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
2answers
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 ...
1
vote
1answer
116 views

Nonalgorithmic and approximate solutions to undecidable problems / formulas?

Wikipedia in https://en.wikipedia.org/wiki/Undecidable_problem defines undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that ...
1
vote
1answer
61 views

Are soundness and completeness necessary for decidability? [closed]

Is it necessary for a logical system to be both sound and complete in order to be decidable?
1
vote
2answers
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 ...
1
vote
1answer
33 views

Is the semidecidability of the valid formula of second order logic dependent upon the semantic?

This is perhaps a stupid question, but I ask it anyway. It seems to me that the semantic comes after and it cannot change the complexity of the language. I ask the question, because Herbert B. ...
1
vote
1answer
101 views

A recursively enumerable theory without a decidable set of axioms.

A theory is a set of first order sentences over some signature. A set of sentences are called axioms for the theory, if the deductive closure of the axioms equals the theory. Now, if I have a ...
1
vote
1answer
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 ...
1
vote
1answer
113 views

Why is ZFC recursively axiomatizable?

I have read that ZFC is recursively axiomatizable, and hence is incomplete by Gödel's theorem. Now why is this true? Consider in particular the axioms of replacement and separation. My guess is that ...
1
vote
1answer
127 views

Is it semi-decidable whether a context-free grammar generates a regular language?

It is a well-known that it is undecidable in general whether an arbitrary context-free grammar generates a regular language. However, I could not find any results concerning the question whether this ...
1
vote
1answer
52 views

Does solving the complexity class ALL collapse all Turing degrees?

I came across this paper by Scott Aaronson and though I understand nothing of quantum computing, the fact that there was an (even hypothetical and probably unrealizable) model of ...
1
vote
1answer
64 views

Is the sign of a real number decidable?

I'm working on the following problem in a class on provability. Consider how $\mathbb{R}$ might be presented. Is the property of being positive decidable? How could the reals possibly be presented ...
1
vote
1answer
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, ...
1
vote
2answers
48 views

Proof in constructive mathematics using decidability.

I am working in constructive mathematics that means without the law of excluded middle. One may also interpret this as working in inuitionistic logic. Lets assume I have some set $A$ such that I ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
2answers
102 views

Is a logic system with predicate symbols, individual constants, negation, and conjunction (no variables and no quantification) decidable?

Suppose I have a logical system with predicate/relation symbols and individual constants symbols, negation and conjunction, but no variables or quantification. For instance, suppose I have the ...
1
vote
1answer
163 views

Are non-computable and undecidable the same?

What is the difference between non-computable and undecidable if any?