Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-5
votes
0answers
174 views

Tarski Undefinability examined under alternative basic assumptions [on hold]

I am taking this to be the generalized result of the Tarski Undefinability Theorem: All formal systems of greater expressive power than arithmetic necessarily have undecidable sentences. (The ...
1
vote
1answer
41 views

Decidability of Gödel sentences.

Letting $\text{Pr}(x)$ be a formula that weakly represents the set $\{x:x\text{ is a Gödel code of a provable sentence in PA}\}$, where PA means Peano Arithmetic. Gödel's first incompleteness theorem ...
0
votes
1answer
61 views

Prove that the following language is decidable / undecidable

Part A) Prove that the following language is decidable: Input: The description of a DFA A. Output: YES if A accepts the empty string. NO if A does not accept the empty string. I am struggling ...
-1
votes
0answers
22 views

Proving $E_{DFA}$ decidability by running $A_{DFA}$ a finite number of times(very tricky)

I am trying to prove that language $E_{DFA}$ is decidable using multiple executions of $A_{DFA}$ (not using the proof in Sipser's book "Introduction to the Theory of Computation"). Can i just use ...
0
votes
1answer
25 views

Show that the decision problem for implication is solvable if and only if the decision problem for validity is solvable

Having trouble with the forward direction of this proof. I assume that the decision problem for implication is solvable, so that for any set of sentences $T$, I can arrive at a yes or no answer to ...
1
vote
0answers
20 views

Is intuitionistic first-order logic with no function or relation symbols decidable?

Classical first-order logic with no function or relation symbols is decidable. If I'm not mistaken, this is essentially because any formula (with possible free variables) has truth value uniquely ...
-4
votes
1answer
193 views

What would be the effect on the Tarski Undefinability proof?

What would be the effect on the Tarski Undefinability proof: If his third equation was correctly decided to be false? 3) x ∉ Pr if and only if x ∈ Tr // page 275 Would the whole proof then fail ...
1
vote
2answers
85 views

Model Theoretical Interpretation of the Incompleteness of Number Theory

This question was sparked by this Numberphile video: https://www.youtube.com/watch?v=O4ndIDcDSGc. Near the end, (12:05), he speaks about the Riemann Hypothesis. He describes that if Riemann is shown ...
6
votes
3answers
2k views

How could Collatz conjecture possibly be undecidable?

I wonder how the Collatz conjecture could possibly be undecidable. Let's say it's undecidable, then no counter example can ever be found, and that to me seems to imply that none exist, and thus that ...
0
votes
1answer
77 views

Difference of two decidable languages?

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their ...
3
votes
0answers
35 views

Why can't the sequent calculus for First-Order Classical Logic be used for proving decidability via Proof-search?

I understand that Turing reduced the halting problem to the satisfiability problem of first-order logic thus proving first-order logic undecidable. However, when thinking about the sequent calculus ...
0
votes
1answer
57 views

Weakened versions of Word and Isomorphism Problems in group theory

Here are my questions: (Weakened Word Problem) Let $\langle X |R\rangle$ be a finite presentation of a group $G$, and let $w$ be an element of the free group $F(X)$. Does there exist an algorithm (...
1
vote
0answers
31 views

Symbols of the language vs. Free variables

For some context: I'm currently taking a course of Formal Methods and Logics and there's a passage where we show that the monadic second order ($\text{MSO}$) theory of (possibly labelled) linear ...
1
vote
1answer
50 views

Can we enumerate finite sequences which have no halting continuation?

Note: this is a cross-post from CS.SE, since I haven't gotten an answer there. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
0
votes
1answer
13 views

Specify a decisive Turing machine that calculates the following function $f$.

Specify a decisive Turing machine that calculates the following function $f$: $$\small f:\{a,b\}^*\to\{a,b\}^*\textrm{ with } f(w)= \begin{cases} (bba)^{3\cdot\#_b(w)}& \text{if } \#_a(w) \text{ ...
1
vote
2answers
31 views

Why does the unsolvability of the Halting Problem give a negative solution to the decision problem?

So Hilbert famously asked for a formalization of all of mathematics which was computationally decidable. Gödel is credited with shattering the idea that "all of mathematics" can be formalized. After ...
2
votes
1answer
74 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 ...
2
votes
1answer
35 views

How Wang's conjecture implies decidability of The Domino Problem?

Wang stated following conjecture about Wang tiles (which was proven false by R. Berger): A finite set of plates [Wang's tiles] is solvable if and only if it has at least one periodic solution. ...
3
votes
1answer
114 views

Is determining derivability in propositional logic decidable?

I know that determining (semantic) entailment in propositional logic is decidable by the truth table method. For instance, let: $\phi = b \rightarrow a \\ \psi = b \lor c \rightarrow a$ Then we can ...
0
votes
0answers
24 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
55 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
17 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
38 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 ...
3
votes
1answer
105 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
37 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
827 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
96 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 $\...
0
votes
0answers
30 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
52 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 ...
1
vote
1answer
113 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
73 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
20 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
48 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
28 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
61 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
160 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
93 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
73 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
53 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
75 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 \...
2
votes
1answer
64 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
59 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
61 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
33 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
60 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(...
2
votes
2answers
81 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
votes
1answer
37 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
127 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 ...
1
vote
1answer
52 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 ...