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.
0
votes
0answers
18 views
does the language 𝐿 = {< 𝑀1 >, < 𝑀2 >: 𝐿(𝑀1 ) ⊆ 𝐿(𝑀2)} is in co-RE?
i was asked to determine if its in RE and if its in co-RE.
well i think its easy to say the language is not in RE but i was wondering if this language is in co-RE.
so the question is if $\overline{L}$...
1
vote
1answer
46 views
proof that specific disjoint sets are recursively enumerable, but don't lie in a decidable set and its complement
let's call a set $A \subseteq \mathbb{N}$ recursively enumerable if it's "partial characteristic function" $\tilde{\chi}_A$ is computable, whereby $\tilde{\chi}_A$ is defined as: $\tilde{\chi}_A$:= 1, ...
0
votes
0answers
23 views
Decidability of a relation on Functional space!
Suppose I have this functional space $(D=\{ a\searrow b; a \in A , b \in B\}, \leqslant)$ (partial order relation on step functions!),also suppose that relation $\leqslant_1$ is decidable on $(A,\...
0
votes
0answers
12 views
If a language is NOT partially decidable, is the complement not partially decidable?
I am trying to figure out if L is partially decidable or not partially decidable.
Let L be {encode(x): x is a Turing machine that halts on input encode(x)}.
2
votes
1answer
36 views
Undecidability of: $|w \in L| \geq 1, L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$
Let $a_0, a_1 \in \mathbb{N} \setminus \{0\}$ and $L=\{w \in \{0,1\}^*|a_0·\#_0(w)+a_1·\#_1(w)- a_1a_0=0\}$ . Let's assume problem $P$ that, language of Turing machine accepts at least one word from ...
2
votes
1answer
49 views
Example of incomplete, but decidable theory, and of complete and undecidable theory, question
On wikipedia it is written that
Decidability should not be confused with completeness. For example, the theory of algebraically closed fields is decidable but incomplete, whereas the set of all ...
0
votes
1answer
35 views
Proving the diagonalization of $U \subset \mathbb{N} \times \mathbb{N}$ that is an universal set for all enumerable sets of naturals is undecidable
Let $U \subset \mathbb{N} \times \mathbb{N}$, and let $U_n = \{ x \mid (n, x) \in U \}$. Let's call $U$ universal for some class $\mathcal{S}$ of subsets of $\mathbb{N}$ if $S \in \mathcal{S} \iff \...
15
votes
2answers
755 views
Gödel's completeness theorem and the undecidability of first-order logic
I'm working through this module, "Undecidability of First-Order Logic" and would love to talk about the two exercises given immediately after the statement of Godel's completeness theorem.
First, ...
3
votes
0answers
86 views
Recursion Theory/Incompleteness Theorems: Computability of sets of formulas in first order logic
I am struggling with the following two problems:
Suppose that $M$ is a structure with finite universe and finite alphabet. Show that the set of formulas $\{\varphi$ $\mid$ for every $M$-assignment $\...
2
votes
1answer
64 views
The (un)decidability of the Tits Alternative for any given (suitably defined) set of groups.
Please forgive me if this question is ill-formed. I don't know much about decidability.
Some Background:
There are problems in combinatorial group theory that are undecidable, such as the word ...
0
votes
0answers
29 views
Decidability of $\forall\exists$ diophantine equations
By saying $\forall\exists$ diophantine equations I mean sentences of the form: $\forall x\exists y\,[p(x,y) = 0]$ where $p$ is a polynomial on $x,y$, and both $x,y$ range over natural numbers.
I want ...
1
vote
1answer
86 views
Why is ZFC recursively axiomatizable?
I have read that ZFC is recursively axiomatizable, and hence is incomplete by Gödel's theorem.
Now why is this true? Consider in particular the axioms of replacement and separation. My guess is that ...
0
votes
0answers
65 views
Halting problem proofs and reduction
Okay so Ive got a problem with the "direction" of reduction and untimately the whole proof, reduction idea as a whole...
My Question is:
Prove that the problem of deciding whether a Turing Machine ...
0
votes
0answers
19 views
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ Is $L_1$ RE or not RE?
I tried to prove $L_1$ is not Recursively enumerable via Rice's theorem, however i've been told by a mentor that examples i used are not valid. Can someone point out the mistakes in my understanding?
...
1
vote
2answers
39 views
Proof in constructive mathematics using decidability.
I am working in constructive mathematics that means without the law of excluded middle. One may also interpret this as working in inuitionistic logic.
Lets assume I have some set $A$ such that I ...
1
vote
0answers
23 views
Decidability context-sensitiv and context-free grammars
Show that it is unsolvable whether a given context-sensitive language is context fre.
And, show that the emptiness problem is solvable for one-way nondeterministic stack automata.
I don't know how ...
1
vote
1answer
35 views
Are soundness and completeness necessary for decidability? [closed]
Is it necessary for a logical system to be both sound and complete in order to be decidable?
3
votes
2answers
132 views
Why is the set of all tautologies in propositional logic recursively enumerable?
I've just started reading an english edition of Gems of Theoretical Computer Science. On page 5 (or page 12 of the overall pdf), the author brings up the set of all tautologies in propositional logic ...
2
votes
1answer
80 views
Large Cardinals and Diophantine Equations (Penelope Maddy)
Professor Penelope Maddy remarks without elaboration in her famous 'Believing the Axioms' essay that
'It should be mentioned that the Axiom of Inaccessibles also has a few extrinsic
merits. It ...
3
votes
1answer
64 views
Algorithm to decide the universality / functional completeness of a set of logic gates?
Given a set of logic gates $G$, let $F_G$ denote the set of all formulas composed of gates from $G$. We say that $G$ is "universal for computation" or "functionally complete" if it forms a basis for ...
1
vote
0answers
49 views
Converting formula to a closed form with only existential quantifiers
Let there be some formula $\phi$, is there an algorithm to construct a closed formula $\phi'=\exists x_1...\exists x_n \psi$ where $\psi$ does not have any quantifiers and $\phi$ is satiable iff $\phi'...
0
votes
1answer
61 views
Prove the theory of equality with a finite number of unary predicates is decidable
Let the signature have $n$ unary predicate symbols $P_1, \dots, P_n$ and a single binary predicate $=$. Consider the theory of equality with the following axioms:
$\forall x (x = x)$
$\forall x \...
1
vote
1answer
41 views
Is there a semi-decidable statement equivalent to the Collatz-conjecture?
We cannot rule out that the Collatz-conjecture cannot be proven. But we also cannot rule out that it is false and we cannot prove this in the case the sequence diverges for some start-number.
Is ...
2
votes
1answer
45 views
Is any context-free grammar in Chomsky form with at most 2017 rules necessarily finite?
A task from one of the former tests:
Is there any algorithm, which for all pairs of context-free grammars over $\lbrace a,b,c\rbrace$ in Chomsky form $G_1,G_2$ with at most $2017$ rules correctly ...
1
vote
1answer
46 views
A axiomatization of (full) Second Order Logic with a decidable proof system cannot be complete; is this true if we only require semi-decidability?
My understanding is that, unlike first order logic, no "effective" (sound, consistent) axiomatization of second order logic is complete; there will always be statements true in all models, but not ...
2
votes
1answer
57 views
Choosing axiom schemes for a logical theory
In a Hilbert system, there are many ways that we can choose axiom schemes. My question is:
1- How do we know that we have defined enough schemes? What would happen if I remove a scheme from the list?
...
1
vote
1answer
29 views
Is the semidecidability of the valid formula of second order logic dependent upon the semantic?
This is perhaps a stupid question, but I ask it anyway. It seems to me that the semantic comes after and it cannot change the complexity of the language. I ask the question, because Herbert B. ...
0
votes
3answers
56 views
Prove whether the problem is decidable [closed]
Main topic is to decide if the problem that selected partial μ-recursive function is an injective function is decidable, undecidable or semi-decidable.
The function is injective when $\forall a,b\;f(...
-1
votes
1answer
36 views
Decidability if a given expression is equal to a prime number
Let us assume there is a number which is well-defined and computable, but it is hard to compute it. E.g., $x=\pi^{(\pi^{(\pi^\pi)})}$. It is not even known if the given number is an integer (which is ...
1
vote
1answer
100 views
Is it semi-decidable whether a context-free grammar generates a regular language?
It is a well-known that it is undecidable in general whether an arbitrary context-free grammar generates a regular language. However, I could not find any results concerning the question whether this ...
2
votes
2answers
65 views
Does double negation elimination hold for decidable formulae in intuitionistic logic?
Let $P$ be a quantifier-free decidable formula, i.e. one can prove $P \lor \lnot P$.
Does it follow that $\lnot \lnot P \to P$ intuitionistically?
Informally, a decidability of a formula means ...
1
vote
1answer
46 views
Does solving the complexity class ALL collapse all Turing degrees?
I came across this paper by Scott Aaronson and though I understand nothing of quantum computing, the fact that there was an (even hypothetical and probably unrealizable) model of ...
2
votes
1answer
83 views
Do given Turing Machines M,N accepts equinumerous languages?
I was doing some exercises from computability and complexity and then I have stuck on this problem:
What type of problem (decidable, semi-decidable, undecidable) is the problem (show it):
Do given ...
0
votes
1answer
27 views
Why is this TM problem decidable
Please explain to me (like I'm an idiot) how the problem Does M on input Λ ever write a nonblank symbol on the tape? given TM M as an input is decidable.
To ...
0
votes
0answers
110 views
Application of Rice's Theorem
How can I prove, by applying Rice's theorem, that the language L is undecidable?
$L = \lbrace \alpha : M_{\alpha}(x) =x^2 \,\,\, \forall x \in \lbrace 0,1\rbrace^* \rbrace $
I think this is a ...
0
votes
1answer
132 views
Prove that every infinite regular language has an undecidable infinite subset
I am having trouble writing a formal proof for this. I understand that we have an infinite regular language. This means that we have uncountable many subsets of the infinite regular language and due ...
2
votes
0answers
51 views
Can the question whether $x^a+y^b+z^c=n$ has a solution over the integers be undecidable?
Suppose, $a,b,c \ge 1$ are integers.
Can the question whether the equation $$x^a+y^b+z^c=n$$ has a solution in integers $x,y,z$ for some particular integer $n$ be undecidable ?
I ask because I ...
0
votes
1answer
107 views
Is First Order Logic + Arithmetic semi-decidable?
I understand that it is not complete, but is it decidable, semidecidable or not decidable? Also, does something have to be complete for it to be considered decidable or semidecidable? Meaning, can ...
1
vote
2answers
155 views
Classify language as decidable, undecidable but recognisable or unrecognizable
I'm currently studying unrecognizable languages in Turing Machines and came across this problem
L1 := {< M > | M is a TM and M accepts at least one string w in {0,1}* with more zeros than ones}
I ...
2
votes
0answers
52 views
Decidability/undecidability of the feasibility of optimization problems
I am building on top of this question on MathOverflow.
The conclusion was that feasibility is decidable. Can one give a direct proof without using heavy machinery like Tarski's theorem?
I do not ...
2
votes
1answer
69 views
Turing machine - Reducible
Given that
Membership Problem is known undecidable
Membership Problem: "Given a Turing machine M and string w, does M accept input w?"
Emptiness Problem: "Given a Turing machine M, is L(M) = ∅ ?"
L(...
2
votes
1answer
65 views
Showing that Presburger arithmetic is decidable by deciding if $\mathbb N \models \varphi$, but does it give provability in the axioms?
Here Presburger arithemtic is given by a set of axioms over the signature with binary operation $+$ and two constants $0$ and $1$. Similarly in Presburgers original paper he gives the arithmetic in ...
2
votes
1answer
51 views
Proving decidability of $(\mathbb N, +)$ with Quantifier elimination and evaluating basic formulas
The original proof of the decidability of Presburger arithmetic goes by Quantifier elimination, for example noting that
$$
\exists x (\underbrace{x + \ldots + x}_{\alpha\mbox{ times}} + b = c )
$$
is ...
1
vote
1answer
82 views
A recursively enumerable theory without a decidable set of axioms.
A theory is a set of first order sentences over some signature. A set of sentences are called axioms for the theory, if the deductive closure of the axioms equals the theory.
Now, if I have a ...
0
votes
0answers
59 views
Decidability of Wang's tiling-problem
I am trying to understand the decidability of Wang's tiling-problem and got some questions for you, because I am not used to the difficult proofs I found on the internet:
The tiling-problem is ...
0
votes
1answer
100 views
Flaw in self-referential proof that all languages are undecidable
I am looking for a flaw in the following incorrect proof, which attempts to prove that all languages are undecidable:
Proof: Suppose for contradiction that there is a decidable language $L$. Then ...
2
votes
0answers
68 views
Literature about decidable and undecidable theories
Is there some modern overview paper about decidable and undecidable theories? Something like Ershov's Elementary Theories or Tarski's Undecidable Theories. Particularly I am interested in result about ...
1
vote
1answer
37 views
Relation between the monadic and two-variable fragment of first order logic
My question is whether there are any inclusions or relations with respect to decidability between the monadic and two-variable fragment of classical first-order logic.
1
vote
1answer
62 views
Is the sign of a real number decidable?
I'm working on the following problem in a class on provability.
Consider how $\mathbb{R}$ might be presented. Is the property of being positive decidable?
How could the reals possibly be presented ...
6
votes
0answers
110 views
The elementary theory of finite commutative rings
I have wondered the decidability of elementary theory of finite commutative rings. Since we know that the elementary theory of finite fields is decidable shown by J.Ax (The Elementary Theory of Finite ...
