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.

315 questions
Filter by
Sorted by
Tagged with
83 views

Decidable but incomplete arithmetical theories?

There are celebrated examples of theories that are both decidable and incomplete (the theory of algebraically closed fields, various toy theories with only finite models). But are there any examples ...
• 95
1 vote
48 views

Is the First-Order Theory Over Reals with Uninterpreted Functions Decidable?

While I understand that the first-order theory of real-closed fields $(\langle \mathbb{R}, +, \cdot, < \rangle)$ is decidable via Tarski's theorem and quantifier elimination, I'm curious about the ...
62 views

Algorithm for Determining Truth of First-Order Sentences in Complex Numbers

Following my previous question Decidability in Natural Numbers with a Combined Function, I realized that there is a spectrum regarding the hardness of deciding whether a first-order sentence is true ...
• 87
90 views

Decidability in Natural Numbers with a Combined Function [closed]

It is well known that there is no algorithm to determine whether a given first-order sentence is true in the structure of natural numbers with both addition and multiplication. In contrast, Presburger ...
• 87
1 vote
25 views

• 152k
81 views

Is Tarski's exponential function problem arithmetically decidable?

https://en.wikipedia.org/wiki/Tarski%27s_exponential_function_problem shows a very interesting problem, as for me begging for an undecidability proof (as the Tarski-Seidenberg theorem itself is ...
1 vote
72 views

Follow up to a previous universal algebra question on decidability of consistency

This is a follow up to my previous question on universal algebra and decidability, here: Is it decidable if a finite set of equations have only trivial models?. In that question, the answerer said ...
• 21.5k
102 views

Undecidable difference of decidable sets.

I have the following problem: Prove that there are decidable sets of natural numbers 𝐴 and 𝐵 such that set $A − B = \{x − y | x \in A, y \in B\}$ is undecidable (𝐴 − 𝐵 is a subset of natural ...
• 33
140 views

If $A$ is decidable, then $A$ is true.

Given is a statement $A$. Now I know the following for this particular statement: If $A$ is decidable, then $A$ is true. What can you conclude about the truth value of $A$? Obviously, if $A$ is true,...
71 views

Is the algorithmic problem for regular languages decidable?

I have an algorithmic problem, where I need to build an algorithm and say if the problem is decidable. Here it is: Regular languages $L_1$, $L_2$, and $L_3$ are given by finite automata. Is the ...
50 views

Undecidability of the theory of multiplication with order

In her paper, "The Theory of Integer Multiplication with Order Restricted to Primes is Decidable" Françoise Maurin claims the following On the other hand, J. Robinson shows in [12] that the ...
• 5,965
1 vote
37 views

Are there terminating methods to provide models of first-order theory formulae?

If a first-order theory is decidable on its existential fragment, does this imply that we have a method (that guarantees termination) to obtain models of existentially quantified formulae within this ...
• 247
1 vote
28 views

Decidability of discrete variable predicate calculus

Question. Is a predicate logic with discrete variables decidable? If yes, than whats is algorithm to obtain statement about truthiness of particular sentence? If yes, it would be good to have ...
• 333
1 vote
73 views

Is it decidable if two structures are isomorphic?

Suppose that $S$ is a nested set and let $S_E$ be the set of "pure" elements (that is, elements of $S$ that are not sets). For example, if $S=\{a,\{a,b,c\}\}$ the "pure" elements ...
• 405