# 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
Filter by
Sorted by
Tagged with
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 ...
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 (...
1 vote
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 ...
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 ...
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....
1 vote
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 ...
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}$ ...
1 vote
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. ...
68 views

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 ...
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 ...
1 vote
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 ...
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) ...
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?
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, ...
1 vote
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 ...
### 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$ (...