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.
187
questions
3
votes
0answers
46 views
Is deciding termination easier than deciding rationality?
Irrationality proofs are usually extremely hard. Unknown cases include the Euler-Mascheroni-constant $\gamma$ , $e+\pi$ and $e\cdot \pi$
Is it easier to decide whether a given number has a ...
0
votes
0answers
30 views
Do the Robinson and/or Peano arithmetics suffice to prove that the Halting problem is undecidable?
Robinson and Peano are both rather weak systems, but they suffice to capture the rules of the natural numbers sufficiently to talk about the Gödel numbering etc., and Kleene's T predicate indicates ...
0
votes
0answers
20 views
Diagonalization for Etm
$E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$
We want a proof by diagonalization to show that $E_{TM}$ is undecidable. But the form of inputs are like $<M>$ and the Table ...
5
votes
1answer
42 views
Decidability Results for $\mathcal{L}_{\omega_1, \omega}$?
Recently I was giving a talk on decidability results in logic and I wanted to emphasize that there is more to life than than just First Order Logic. In particular, I made sure to include results such ...
1
vote
0answers
36 views
Degree 2, 3 variable homogenous instance for Hilbert's Tenth Problem
I know that Hilbert's Tenth problem is uncomputable as shown by Matiyasevich's theorem, but for a special case, is Hilbert's tenth problem decidable for degree two homogenous $3$ variable instance of ...
1
vote
0answers
137 views
Given a Turing Machine $M$ and a word $w$, can we tell if the Turing Machine will move its head at every step?
The exercise I'm trying to solve is: Is the language $L = \{<M>,w\ |\ M \text{ moves its head on input } $w$ \text{ at every step}\}$ decidable or undecidable.
We work with a version of the TM ...
0
votes
0answers
12 views
Prove that the problem [input is program Q and the question is does Q calculates the function f(y)=y^2] is undecidable
I need to prove the following problem is undecidable: Input for the problem is: A program called Q; The question is: does the program Q calculates the function f(y)=y^2;
My solution is: Reduction from ...
1
vote
1answer
80 views
Peano Arithmetic - Decidability
I need to show that if Peano Arithmetic does not decide a sentence $\varphi$ then the standard model
of Peano Arithmetic satisfies the negation of $\varphi$.
I know this partly has to do with Godel's ...
0
votes
0answers
117 views
What to do with undecidable problems?
Several fundamental problems in math are undecidable; see the sphere recognition problem for example. To make it worse, quantum computers will not help. Therefore, I wonder what we can do about ...
0
votes
1answer
60 views
Is it true that every closed formula is decidable? Why?
I was wondering if every closed formula is decidable (in a complete system). Clearly a non closed formula is not decidable, since it can take some values for which it is true, and other for which it ...
0
votes
1answer
46 views
Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?
So I just started learning about computability, undecidability and Turing machines. And I wonder if:
Given a computable and injective function $f$, is $f^{-1}$ also computable and injective?
I don't ...
2
votes
1answer
33 views
Why is it enough to test only the words up to length n ( number of state) in the given algorithm for a decidability problem
My question is related to the problem below, basically it's a decidability problem and the algorithm prooves it's decidable.
My question :
After reading the step 2 of the algorithm below, why is it ...
0
votes
1answer
38 views
How to show that this language is Turing recognizable
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show ...
0
votes
1answer
44 views
If L1 is decidable and if L2 is included in L1, is L2 also decidable?
Is this statement true or false and why ?
If $L_{1}$ is decidable and if $L_{2}$$\subseteq$$L_{1}$ then $L_{2}$ is also decidable.
I would be tempted to say yes, but i am really not sure. I am also ...
2
votes
1answer
82 views
How to show that this language is decidable
The question :
The language is $L=$ { $< G,w > $ : $G$ is a grammar in normal form of Chomsky and $w$ is a word on the terminal alphabet that can be derivated in $G$ by at least 2 differents ...
4
votes
1answer
153 views
NP, NP-complete and Reducibility
Suppose there is polynomial time reduce from problem $A$ to $B$.
fact $1)$ if problem $B$ is $NP$-hard then Problem $A$ is $NP$-complete.
fact $2)$ if problem $A$ is $NP$-complete then Problem $B$ is $...
2
votes
1answer
81 views
Show that the following language is decidable by finding the algorithm for the finite automaton
Given the language $K$ = $\{<M>: M$ is a finite automaton on the alphabet {0,1}) and $L(M)$ contains at least one word of the form $0^k1^l$ with $k,l\geq 0$}. In other words, describe an ...
1
vote
0answers
46 views
Show that this language is undecidable
Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$
I would like to know if ...
1
vote
1answer
38 views
Best approach for Undecidability proof
Context:
Hi, my professor sent me this challenge and I got stuck. I thought using Rice's Theorem for this question, since $M$ is non-trivial, but he told me to use a reduction.
Is he right? Should I ...
0
votes
1answer
56 views
show this language is undecidable
$L = \{ \langle G \rangle \mid G$ is context-free, $L(G)$ contains a palindrome $\}$
Reduce the post correspondence problem to $L$.
So I have to show that if I could decide L then I could decide PCP.
...
-1
votes
1answer
34 views
Boolos’s proof of the first incompleteness theorem. Predicate $C(x,y)$ and assumption of completeness.
I am trying really hard to understand how Boolos’s proof works, but I keep having doubts about it. Can you spot any logical flaws in my reasoning? This question arose from a previous question of mine, ...
0
votes
2answers
36 views
Show that $G_{u,v}$ is not decidable and not recognizable (nor is its complement)
Let $\Sigma$ be an alphabet, $u,v \in \Sigma^*, u \neq v$.
$G_{u,v} = \{ \langle M \rangle \mid M$ is turing machine, $u \in L(M) \Leftrightarrow v \in L(M)\}$.
I understand that if it is not ...
0
votes
0answers
20 views
Are the following languages decidable?
$L_2 = \{ \langle M \rangle \mid M $is a turing machine, there is a different turing machine M' with $L(M')=L(M) \}$
$L_4 = \{ \langle M \rangle \mid M(\varepsilon) $writes three consecutive 1s at ...
0
votes
0answers
23 views
$\mathsf{DSPACE}(n) \subsetneq \mathbb{E}$: there is a decidable language no LBA can handle..
Use the following lemma and diagonalisation:
Lemma: Let $M$ be a linear bounded automaton. Then, there is a lba $M'$, that accepts the same language and halts on every input.
($\mathsf{DSPACE}(n)$ is ...
1
vote
1answer
29 views
Show that the following language is decidable
$E_{cfg}=\{ \langle G \rangle \mid G \text{ is context-free grammar}, \ L(G)=\emptyset \}$
I think the following algorithm should work:
Test whether or not the input $w$ codes a cfg. If not, reject.
...
3
votes
2answers
106 views
Has Any Currently Open Problem in Mathematics Definitively Been Shown to be Decidable?
There is a fairly extensive list of problems in various fields that have been shown to be undecidable. For example, see
https://en.wikipedia.org/wiki/List_of_undecidable_problems
And certainly, an ...
0
votes
0answers
46 views
Decidability of convergence of real series given an oracle for positive series
I've been reading for the last hour a few posts on this site about series that no one knows if they converge or not. I was quite surprised that they were almost all consisting of positive terms.
...
0
votes
1answer
287 views
Boolos’s proof of Gödel’s first incompleteness theorem. What am I getting wrong?
Sorry in advance, the following is quite messy, I didn’t find a way to express myself more clearly and rigorously. I would appreciate suggestions on how to make the following better and try to act ...
-6
votes
1answer
166 views
Gödel's first incompleteness theorem. What did I get wrong? [closed]
I'd like to point out that obviously I don't claim the following to be right, and I now recognise that the way my question was phrased before editing could have been interpreted as very arrogant, and ...
7
votes
1answer
87 views
Open problems in the first order theory of the real numbers
It is a well-known result that the first-order theory of the real numbers is decidable. However the decision algorithm for this language is in double exponential time, so such an algorithm cannot be ...
2
votes
1answer
40 views
Prove decidability. Sets A and B. B is finite (have inite number of elements), A is undecidable. Can $A$ $cup$ $B$ be decidable?
Sets $A$ and $B$. $B$ is finite (have inite number of elements), $A$ is undecidable. Can $A$ $\cup$ $B$ be decidable?
I have and idea, but i'm not sure that it's correct.
What if $A \cup B$ is ...
0
votes
1answer
43 views
Prove the decidability of an enumerable set. A and B are enumerable, C is decidable.
Sets A and B are enumerable, C is decidable. $A$ $\subseteq$ $C$ $\subseteq$ $A$ $\cup$ $B$. $A$ $\cap$ $B$ = $\emptyset $.Prove that A is decidable too
1
vote
1answer
27 views
Is the statement $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B \land A\in \operatorname{REC}\implies B\in\operatorname{REC}$ true?
Is the statement $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B \land A\in \operatorname{REC}\implies B\in\operatorname{REC}$ true?
I know, that $A \leq_{\operatorname{mo}}^{\operatorname{poly}}B$...
1
vote
1answer
73 views
How close is “$Y$ is connected” to a $\Sigma^0_1$, or $\Pi^0_1$ sentence?
I was giving some thought to this answer and I was curious about the sentence
$Y$ is connected
How close is $Y$ is connected to a $\Sigma^0_1$, or $\Pi^0_1$ sentence?
For a little more context... ...
0
votes
0answers
63 views
How to disprove that a problem is undecidable
My question is similar a question already asked
Decidability of the Riemann Hypothesis vs. the Goldbach Conjecture
But in general, given some well-known problems of mathematics for example the Riemann ...
3
votes
1answer
38 views
Given a TM T , is there an input string that causes T to enter every one of its nonhalting states?
Given a TM T , is there an input string that causes T to enter every one of its nonhalting states?
I think it is undecideable and want to use reduction to prove it, but can't think of an undecideable ...
0
votes
1answer
18 views
Prove that: For each language L that is accepted by a DTM in polynomial time, there is also a DTM M′ that decides L in polynomial time.
According to one of my professors, the statement "For each language L that is accepted by a DTM in polynomial time, there is also a DTM M′ that decides L in polynomial time." is true, but i ...
0
votes
1answer
50 views
Decidable Languages over an alphabet
How can we prove that exist as many decidable languages over {1, 0} as over the
alphabet {0}.
I understand that the number of turing machines over an alphabet is countable. But how can we formulate a ...
0
votes
0answers
32 views
Is there a “basis” or “subbasis” for semidecidability?
There seems to be an analogy between semidecidability and topology, but to me, the "topology" seems to be weak. The usual definition of a topology over a space $X$ is:
Statement #1: $\...
1
vote
1answer
198 views
An undecidable problem and a non-semidecidable one
Prove that the decision problem "Does $f$ match this behaviour?" is undecidable (assume the behaviour is nontrivial) and that the problem "Is $h(x)$ undefined?" is not semi-...
0
votes
0answers
48 views
Decidability of $2^a \bmod a^3$?
From some limited testing, it seems to me like $2^a \bmod a^3$ has no repeat values except for some powers of $2$. More generally, it also seems that $x^a \bmod (a^3+k)$ often holds to this, although ...
3
votes
2answers
109 views
Is Hilbert's tenth problem decidable for degree $2$?
Hilbert's tenth problem is the problem to determine whether a given multivariate polyomial with integer coefficients has an integer solution. It is well known that this problem is undecidable and that ...
1
vote
1answer
32 views
Separation axiom implied by semidecidability of comparison
I am studying computable analysis. What I'm fascinated by is the analogy between computable analysis and general topology: a Wikipedia article
Semidecidable sets are analogous to open sets.
So I ...
0
votes
1answer
28 views
Prove decidability or undecidability of a language accepted by a turing machine.
consider this problem:
"Given a TM $X$, determine if the language accepted by $X$ contains more than $100$ strings"
Is this problem decidable or not?
Opinion 1: (mine)
I derived my proof by ...
1
vote
1answer
55 views
Prove that $L=\big\{\langle G\rangle \mid G\text{ is a CFG over }\Sigma=\{0,1\}\text{ and }1^* \cap L(G)\ne\varnothing\big\}$ is decidable.
How to prove that $L = \big\{\langle G\rangle \mid G \text { is a CFG over } \Sigma = \{0,1\} \text { and } 1^* \cap L(G) \ne \varnothing\big\}$ is decidable? I know I am supposed to prove that it is ...
2
votes
1answer
74 views
“Natural” example of an undecidable subset of $\Bbb N$
All the simple examples of undecidable problems that I know deal with symbolic computation or calculation. For example, the halting problem, whether Diophantine equations have solutions, the word ...
0
votes
0answers
26 views
What does “L being a CFL” as “a property of CFL's” mean?
In Ullman's Introduction to Automata, Languages and Computation (1979):
8.8 Use Theorem 8.14 to show that the following properties of CFL's are undecidable.
a) L is a linear language.
b) L is a CFL.
...
1
vote
0answers
48 views
Why is the blank-tape halting problem $H_0$ so relevant in literature?
After comparing some text books and lectures about computability theory I encountered not only the halting problem
$$H = \{\langle M,x \rangle \mid \text{the Turing machine $M$ halts on input $x$}\}$$
...
1
vote
0answers
32 views
Is there any example of a property which is true but undecidable?
Yesterday I thought I had found a paradox about undecidable statements. Let's say there is some property P about integers, which is formulated as follows: ∀ n ∈ ℕ, something(n). Where "something" is a ...
1
vote
0answers
63 views
Necessity of decidable type checking for formalizing mathematics
If a type theory such as Martin-Löf's dependent type theory (MLTT) is to be used as a foundation for mathematics, decidable type checking is certainly nice to have: it guarantees that for every proof ...
