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.
292
questions
2
votes
1
answer
49
views
Number of bitstrings where any subpattern repeats at most $d$ times
The following problem has come up in the context of unitary equivalence of sets of matrices. However, here I will omit the context and state it as a standalone combinatorial problem.
Consider ...
- 133
0
votes
2
answers
115
views
How to understand Tarski’s Real Closed Field theory result
The decision problem I have is: the truth values of any First Order Logic sentences that contain arithmetic operations and equalities/inequalities on any real numbers.
Per Tarski’s Real Closed Field (...
- 33
1
vote
0
answers
55
views
Decidable formal language with a finite but non-computable size
I'm looking for a formal language that has the following properties:
Contains finitely many words (and you can prove it).
Decidable/recursive (there's a Turing machine that always halts, that can ...
- 113
4
votes
0
answers
58
views
Is it decidable if a finite set of identities imply the commutative identity?
This is a follow-up to my previous question, here: Is it decidable if a finite set of equations have only trivial models?. Let our signature be that of a single binary operation symbol $*$. Suppose I ...
- 18.5k
0
votes
1
answer
70
views
Proof for halting problem is recursively enumerable
So, I know the proof for Halting Problem is not recursive using diagonalization. We prove it using proof by contradiction. First we assume HP is recursive which implies there is a Total Turing Machine....
- 3
1
vote
0
answers
41
views
Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof
all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct?
TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
- 145
5
votes
1
answer
248
views
Number of unpaired $x$ and $y$ samples needed to determine $A\in\mathbb{R}^{2\times2}$
This is a question from an exam on deep learning that I took not so long ago, and I'd like to know the answer.
The Setting
There is a Gaussian distribution from which we sample $x \in \mathbb{R}^{2}$ ...
- 411
1
vote
2
answers
102
views
Is cardinality of the set of real number between 0 and 1 that doesn't have some specific digit string in some specific base decidable?
Originally, I get this idea when I try to create intermediate cardinality set between the integers and the real numbers to disprove the continuum hypothesis when I read the normal number definition.
...
2
votes
2
answers
68
views
Does "defined by cases" only work for decidable sets or also for semi-decidable sets?
If $A,B\subseteq\mathbb{N}$ are disjoint decidable sets then it is
clear to me that function $f$ is defined as:
$f\left(x\right)=\begin{cases}
1 & \text{if }x\in A\\
2 & \text{if }x\in B\\
\...
- 149k
0
votes
0
answers
44
views
Decidability of the universal algebra consistency problem of the bi-unary signature
This is yet another follow up to my previous question on universal algebra and decidability of consistency, here: Follow up to a previous universal algebra question on decidability of consistency. In ...
- 18.5k
2
votes
0
answers
60
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
1
answer
69
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 ...
- 18.5k
3
votes
1
answer
69
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
2
votes
1
answer
103
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,...
user1114342
0
votes
1
answer
67
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 ...
0
votes
1
answer
48
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,655
0
votes
0
answers
38
views
Prove that the following problem is undecidable by a reduction from the halting problem:
Prove that the following problem is undecidable by a reduction from the halting problem:
“Does a given Turing Machine M accept any string of form a^2k for k ≥ 1?”
I'm having trouble understanding the ...
0
votes
0
answers
10
views
trivial reduction for undecidability in complexity theory.
Can the reduction if $w \in A$, then we red(w) for all w mapped to a constant element which we know $red(w) \in B$ and similarly for $w \notin A$ we map to a single different $red(w) \notin B$?
This ...
1
vote
0
answers
32
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
0
answers
23
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 ...
- 321
1
vote
1
answer
63
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
0
votes
0
answers
62
views
which notion of provability in Turing's paper 1936?
In Turing's article 1936 https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Turing provides a proof in §11 p.259 for the Hilbert decision problem "Entscheidungsproblem".
p. 259 he ...
- 167
1
vote
1
answer
72
views
What does it mean to say that a formal theory is recursive
The wikipedia article on Formal Theories states that
"A formal system is said to be recursive (i.e. effective) or recursively enumerable if the set of axioms and the set of inference rules are ...
3
votes
1
answer
128
views
How do we know whether a certain statement is provable or not?
Certain statements are known to be unprovable within a given axiomatic system; the continuum hypothesis within ZFC is an example. We can either add the continuum hypothesis, or its negation, to ZFC, ...
- 198
0
votes
1
answer
147
views
It is possible to show ($HALT_{TM}$ is decidable $\Rightarrow A_{TM}$ is decidable), but how about the converse?
Let $HALT_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ halts on } w \}$ and $A_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ accepts } w \}$.
It is possible to ...
- 1,873
3
votes
1
answer
103
views
Would undecidability of $P = NP$ imply its truth/falsity?
Suppose someone proved that the $P = NP$ question is undecidable from $ZFC$. Would that imply it is true? Would that imply it is false? I know that there are certain mathematical statements which, if ...
- 18.5k
3
votes
0
answers
63
views
What is the quartic undecidable Diophantine equation with 58 unknowns that's undecidable?
I found in Jones' 1980 work "Undecidable Diophantine Equations" Theorem 4 that it is claimed that at least one 58 unknown quartic Diophantine equation is known to be undecidable. It is not ...
- 31
0
votes
1
answer
47
views
Can you prove that the difference of these two undecidable sets is un/decidable?
I'm just an amateur programmer so please bear with me
consider the following sets of numbers
$$
D=\{m|\text{$m$ is a turing machine and does not halt on blank input}\}
$$
$$
G=\{m|\text{$m$ is a ...
- 103
-1
votes
3
answers
162
views
Is "$X$ is finite" decidable (in ZFC)?
Disclaimer: This question is about formalizing the idea that a particular set is "finite" in strict first-order ZFC, without any extensions or informal statements, except where otherwise ...
- 4,634
0
votes
0
answers
41
views
Theory of real numbers is decidable but Peano arithmetic is undecidable? [duplicate]
How can the theory of real numbers be decidable while Peano arithmetic is not? Why can't Godel numbering be used to demonstrate a true but unprovable sentence given that the natural numbers that are ...
- 1,420
0
votes
0
answers
33
views
Proving in computability if L is subset of RE and infinity there is A ⊆ L and decidable
I'm trying to prove this in Computability:
if $L$ is a subset of Recursively Enumerable \ Recursively ($RE \setminus R$) and $L$ is infinite,
so there is $A \subseteq L$, which is infinite and ...
- 11
0
votes
0
answers
49
views
Decidability of the Membership problem
Good day!
I have the following question.
Given a subset S ⊆ N = {0, 1, 2...}, the S-Membership problem asks "Given a number n ∈ N, is n in S"?
We call the set S decidable iff its S-...
- 29
0
votes
1
answer
36
views
Can we prove that $L_1$ is decidable?
Let $L_1, L_2 \subseteq \Sigma^*$ be Turing recognizable languages. Suppose there is a computable function $f : \Sigma^* \to \Sigma^*$ such that $x \notin L_1 \to f(x) \in L_2$. Can we prove that $L_1$...
1
vote
1
answer
45
views
Is the converse of Hilberts 10th problem decidable?
I was wondering if the following problem has been studied and if so where I could find work on it:
Given a set of integer solutions S. Is there a polynomial with integer coefficients that has exactly ...
- 61
2
votes
1
answer
96
views
A definability paradox for infinite binary sequences
Consider the set of infinite binary sequences $\{0,1\}^\omega$. Also consider some finite alphabet $\Sigma$, the set of all finite symbol sequences $\Sigma^{\mathbb{N}}$ that can be made from the ...
- 3,491
0
votes
0
answers
85
views
Proving that a language is Turing reducible to halt
I'm trying to complete the proof to show that language L is Turing reducible to HALT. Here is the problem:
Let $𝐿 = \{< M > | 𝐿(𝑀) = \{'X'\}\}$.
Prove that
$𝐿 \leq_T 𝐻𝐴𝐿𝑇$.
How would I ...
- 1
0
votes
1
answer
72
views
Is the decision problem of compiling a program decidable?
Let C be a compiler, an abstract machine consisting of the following procedures:
Preprocessing
Syntactic analysis
Semantic analysis
Intermediate representation
Optimization
Code generation
that ...
0
votes
0
answers
36
views
Deciding first order logic with constant exponentials
It is known that (R, +, *, <, 0, 1) is decidable by Tarski.
If we add a symbol for the exponential function exp(x) (where <...
- 125
0
votes
0
answers
51
views
Nelson-Oppen: Does 'quantifier-free' mean that is decidable?
Given two theories $T_1$ and $T_2$ with disjoint-signatures
$Σ_1$ and $Σ_2$ respectively, and a conjunction of literals $φ$ over
$Σ_1 \cup Σ_2$, we want to decide if $φ$ is satisfiable under $T1∪T2$. ...
- 247
0
votes
0
answers
60
views
How to efficiently enumerate all valid propositional formulas from implicational fragment of intuitionistic logic?
A set of valid Propositional logic formulas is decidable. A set of implicational propositional formulas is a subset of this set. If we limit Axiom schemas by removing Axiom schema 3 (Peirce's law) we ...
- 415
4
votes
3
answers
153
views
Determining if lattice elements are equal
I am working in a distributive lattice with top and bottom elements.
I would like to know if there is an algorithm to determine if $s=t$ for any two elements $s,t$ in the lattice. For example, if $t=s\...
- 369
0
votes
0
answers
42
views
How does the independence of the continuum hypothesis from ZFC square with the law of excluded middle? [duplicate]
So this is a follow-up to this question of mine. According to the answers there so far, the law of excluded middle (i.e. the notion that $\varphi\vee\neg\varphi$ is true for all wffs $\varphi$ for ...
- 2,417
0
votes
1
answer
123
views
Does the law of excluded middle hold in first-order logic?
In propositional logic, we create well-formed formulas out of logical connective symbols and propositional variables. Then we can consider a valuation function that first assigns a true/false value to ...
- 2,417
1
vote
0
answers
82
views
A paper states $\exists^*\forall^*$ modulo Linear Integer arithmetic (LIA) is undecidable, but I I thought LIA on its own was already decidable
I am reading the following paper, On the Combination of the Bernays–Schönfinkel–Ramsey Fragment with Simple Linear Integer Arithmetic: https://arxiv.org/pdf/1705.08792.pdf
In the introduction it ...
- 247
3
votes
1
answer
99
views
Examples of Exists-Forall-decidable first-order theories that are not overall decidable?
I am looking for first-order theories that are decidable on its $\exists^*\forall^*$ fragment, but I am really struggling with it.
I mean, I know there are lots of theories that are (overall) ...
- 247
3
votes
1
answer
123
views
Why are subclasses of first-order logic with the finite model property decidable?
The title really says all:
Why are subclasses of first-order logic with the finite model property decidable?
- 75
0
votes
1
answer
62
views
Is there an effective decision procedure for determining whether a truth-tree of first-order logic is infinite?
Reading Tomassi's Logic, he says that the truth-tree method is effective in establishing the validity of a valid sequent of first-order logic, and the invalidity of some invalid sequents. However, ...
- 23
1
vote
0
answers
85
views
What is the proof that equational logic is undecidable?
Following section 8 of Equational Logic by George McNulty, I understand the approach of reducing this decision to the halting problem by modelling Turing machines with equational theories. The ...
- 157
0
votes
2
answers
107
views
How to construct a semi-computable set?
How can I construct/define arbitrary semi-computable (but not computable) sets?
Recall that a set A is semi-computable if it is domain of a computable function f. Recall also that a set A is ...
11
votes
0
answers
215
views
Is mate-in-$n$ problem for Trappist-1 undecidable?
Trappist-1 is a variant of infinite chess that has a piece called huygens which leaps any prime number of squares orthogonally. To actually implement this game, it should have decidable mate-in-$0$ (...
- 1,242