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.

Filter by
Sorted by
Tagged with
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 ...
Henrik's user avatar
  • 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 (...
Mike's user avatar
  • 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 ...
koorkevani's user avatar
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 ...
user107952's user avatar
  • 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....
Mike's user avatar
  • 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 ...
boinka's user avatar
  • 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}$ ...
Ariel Yael's user avatar
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. ...
Just a man in the world's user avatar
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\\ \...
drhab's user avatar
  • 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 ...
user107952's user avatar
  • 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 ...
Alexey Slizkov's user avatar
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 ...
user107952's user avatar
  • 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 ...
Andrew's user avatar
  • 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,...
user avatar
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 ...
Vladyslav Chobotok's user avatar
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 ...
user1868607's user avatar
  • 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 ...
Suleyman Kiani's user avatar
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 ...
Yi Yao Tan's user avatar
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 ...
Theo Deep's user avatar
  • 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 ...
Alex Alex's user avatar
  • 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 ...
T. Rex's user avatar
  • 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 ...
huurd's user avatar
  • 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 ...
saulkripke321's user avatar
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, ...
Latrace's user avatar
  • 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 ...
tcmtan's user avatar
  • 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 ...
user107952's user avatar
  • 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 ...
Ning Bao's user avatar
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 ...
raoof's user avatar
  • 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 ...
R. Burton's user avatar
  • 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 ...
Hank Igoe's user avatar
  • 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 ...
ItamarK's user avatar
  • 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-...
Alex Cotreny's user avatar
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$...
throwaway-12062022150610's user avatar
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 ...
julian's user avatar
  • 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 ...
aghostinthefigures's user avatar
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 ...
jamess's user avatar
  • 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 ...
Otávio Augusto Silva's user avatar
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 <...
incaseoftrouble's user avatar
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$. ...
Theo Deep's user avatar
  • 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 ...
Oleg Dats's user avatar
  • 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\...
Eoin's user avatar
  • 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 ...
Maximal Ideal's user avatar
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 ...
Maximal Ideal's user avatar
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 ...
Theo Deep's user avatar
  • 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) ...
Theo Deep's user avatar
  • 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?
Ranias's user avatar
  • 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, ...
Spailpín's user avatar
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 ...
Owen's user avatar
  • 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 ...
SHC MostWanted's user avatar
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$ (...
Ris's user avatar
  • 1,242

1
2 3 4 5 6