Skip to main content

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
5 votes
1 answer
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 ...
ac2357's user avatar
  • 95
1 vote
1 answer
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 ...
bytemouse's user avatar
3 votes
1 answer
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 ...
Toobatf's user avatar
  • 87
-1 votes
1 answer
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 ...
Toobatf's user avatar
  • 87
1 vote
0 answers
25 views

Prove that the set of RAMs which do not calculate the identity function is not recursively enumerable.

"Let $M_0,M_1,...$ be a Gödel Numbering of RAMs. Prove that $B\notin\text{RE}$ and $\overline{B}\notin\text{RE}$, whereas $B=\{i\in\mathbb{N}\;|\;M_i\text{ calculates the function id}:\mathbb{N}\...
arlidenCasper's user avatar
0 votes
0 answers
44 views

Decidability and Semi-Decidability of Languages Defined by Turing Machines

Let's define the input alphabet (A = {0, 1}) and the tape alphabet (T = {0, 1, B}). Let (U) be a universal machine. For a word ($w \in A^*$), we define the Turing machine ($M_w$) as follows: if (w) is ...
Weronika L's user avatar
1 vote
0 answers
93 views

What is the proof that Term Finding in Calculus of Constructions ($\lambda{C}$) is undecidable?

It is mentioned in a textbook "Type Theory and Formal Proof: An Introduction", but couldn't find the paper or proof anywhere on the internet. To quote the textbook: The question of Term ...
Vivek Joshy's user avatar
1 vote
1 answer
61 views

Can a Turing Machine decide if a language is regular, in general?

Can a Turing machine decide/recognize if a given language is regular, in general? $ REG_{TM}=\{\langle M\rangle|\langle M\rangle \text{ is a TM and }L(M) \text{ is regular}\} $ I'm pretty confident ...
Carter Karl Falkenberg's user avatar
0 votes
1 answer
79 views

Questions about part of the proof of the general Halting Problem based on the string procedure [closed]

When reading mcs.pdf, it says in chapter 8.2: $P_s$ definition When a string $s \in \text{ASCII}^*$ is actually the ASCII description of some string procedure, we’ll refer to that string procedure as ...
An5Drama's user avatar
  • 416
3 votes
2 answers
344 views

Turingmachine for decision of mathematical conjecture

A consequence of the Halting-Problem is that there isn't a Turingmachine for the Entscheidungsproblem of Hilbert. An exersice I have to work on has the question: Does there exist a TM that prints 1 if ...
SooS's user avatar
  • 31
0 votes
1 answer
21 views

Does undecidability allow infinite number of algorithms for limited ranges?

Do I understand correctly that undecidability does not preclude the existence of an infinite number of algorithms that, in the limit, would be able to decide $x$'s membership in a set? Of course, this ...
spacemonkey's user avatar
3 votes
2 answers
222 views

Proving a corollary of Trakhtenbrot theorem

In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows: Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
John Davies's user avatar
2 votes
0 answers
72 views

Deciding a circle rotation reachability problem?

Let $x \in [0,1]$ be an irrational algebraic number, and $y \in [0,1]$ algebraic. Does there exist an effective procedure for determining whether there exists some integer $k \geq 1$ such that $$ kx \...
user918212's user avatar
5 votes
1 answer
150 views

Why is the number 3 come up so often in Chaos theory and Undecidability as a boundry? Is it just a coincedence?

What I mean is that the number 3 comes up a lot in these fields as sort of a boundary between decidability and undecidability, or chaos and order. Examples: Quadratic Diophantine equations are always ...
Colonizor48's user avatar
2 votes
1 answer
45 views

Relationship between function decidability and set decidability

Let $\Sigma$ denote an arbitrary language. If $\omega = \mathbb{N} + \{ 0\}$, a $\Sigma$-mixed function is a function s.t. $\mathcal{D}_f \subseteq \omega^n \times \Sigma^{*m}$, with $n, m, \geq 0$, ...
lafinur's user avatar
  • 3,468
1 vote
1 answer
96 views

Is calculability calculable?

I m not at all a specialist so im gonna say how i understand the terms i use even if it's basic for some so we are in the same page. Notation: let $P$ be a turing machine $P(t)$ is the word writen ...
Guill Guill's user avatar
0 votes
1 answer
46 views

Is it decidable whether a classically valid first-order formula is also intuitionistically valid?

Intuitionistic first-order predicate logic is not decidable for arbitrary formulas. However, suppose that we are given a formula of first-order predicate logic that is classically valid. Is there a ...
Adam Dingle's user avatar
0 votes
2 answers
77 views

Why is this undecidability proof for $E_{TM}$ valid?

I understand what it means to reduce a problem and how this is used to show by contradiction that the theorem is true. Question What troubles me is the way the proof is formulated. In step 1.2 it is ...
Noah S.'s user avatar
0 votes
0 answers
22 views

Undecidability of CFG subtraction under a co-finiteness assumption

Fix a finite alphabet $\Sigma$ for the entire discussion. There is a rather obvious proof that the difference of two context-free grammars $A$ and $B$ (compute the language $L(A) - L(B)$) is not ...
V0ldek's user avatar
  • 101
3 votes
1 answer
93 views

Would the Following Table Strategy Work as an Intuitionistic Decision Procedure?

I had previously sought some insight for handling logical operators in the Rieger-Nishimura lattice and, with assistance here, was able to work out a fairly rigorous way. To the best of my ability, I ...
Joshua Harwood's user avatar
0 votes
1 answer
84 views

How to prove that the set of theorems of any recursively axiomatized theory is a recursively enumerable set?

I read the article Craig's theorem written by Putnam (1965). I don't understand the claim on page 3 of the article: The set of theorems of $T$, where $T$ is any recursively axiomatized theory, is ...
유준상's user avatar
4 votes
1 answer
167 views

A reference for undecidability of "$|A|> |B|$ implies $|\mathcal{P}(A)|>|\mathcal{P}(B)|$" in ${\rm ZFC}$.

Note: This is a reference-request question and thus doesn't need the usual type of context. According to this: It is a surprising fact that the statement $$A > B \implies \mathcal{P}(A) > \...
Shaun's user avatar
  • 45.8k
10 votes
0 answers
277 views

Turing-complete recursive function using only $a^b$ and $\log_b a$

Edit: Below, I establish this for $\{\log x,x^y,-1\}$. It occurs to me that you can trade the requirement of including $-1$ for the ability to use a log with any base. This follows because given an ...
Trevor's user avatar
  • 6,014
0 votes
0 answers
42 views

Clocked Turing Machine in Undecidability proofs

If we are dealing with the following reduction: $$\overline{K} \leq \{ p ∣ \forall y: M_p(y) \downarrow \} $$ one of the possible definitions for $M_p[x](y)$ is the following: ...
houda el fezzak's user avatar
0 votes
1 answer
337 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
codeing_monkey's user avatar
1 vote
1 answer
52 views

Inequality of two real numbers is semi-decidable

Equality of two real numbers is undecidable In the above, it is stated that inequality of two reals is semi-decidable. While this is intuitive (check the digits one by one until one differ), I would ...
user avatar
1 vote
0 answers
16 views

Proving undecidability of a problem by showing that a single instance is undecidable

In our theoretical computer science class, we are currently working with undecidable problems on Compositional Message Sequence Graphs (CMSGs). We proved in the lecture, that the existence of a safe ...
EricHier's user avatar
  • 111
0 votes
1 answer
72 views

Problems with universal encoding format for Turing Machines?

When one talks about decidable and semi-decidable languages, it is inevitable that the concept of "encoding a Turing machine as a (binary) string" will come up. And at first glance this ...
adam dhalla's user avatar
0 votes
0 answers
78 views

How is $f_1(n)$ not computable but $f_2(n)$ is? [duplicate]

I came across these two introductory examples on the topic of computable. $$f_1(n) = \begin{array}{cc} \Bigg \{ & \begin{array}{cc} 1 & ,\text{if n appears in the decimal ...
Just Curious's user avatar
1 vote
0 answers
86 views

What is decidability and completeness?

A formal system comes with both a syntactic component, which determines the notion of provability ($\vdash$), and a semantic component, which determines the notion of truth ($\vDash$). For this ...
user avatar
2 votes
1 answer
57 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
306 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
64 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
64 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
  • 21.5k
0 votes
1 answer
331 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
52 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
  • 151
5 votes
1 answer
251 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
118 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
3 votes
2 answers
83 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 the 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
  • 152k
2 votes
0 answers
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 ...
Alexey Slizkov's user avatar
1 vote
1 answer
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 ...
user107952's user avatar
  • 21.5k
3 votes
1 answer
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 ...
Andrew's user avatar
  • 33
2 votes
1 answer
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,...
user avatar
0 votes
1 answer
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 ...
Vladyslav Chobotok's user avatar
0 votes
1 answer
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 ...
user1868607's user avatar
  • 5,965
1 vote
0 answers
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 ...
Theo Deep's user avatar
  • 247
1 vote
0 answers
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 ...
Alex Alex's user avatar
  • 333
1 vote
1 answer
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 ...
T. Rex's user avatar
  • 405
0 votes
0 answers
68 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
152 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

1
2 3 4 5
7