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.
250
questions
0
votes
0
answers
24
views
Undecidibily of the Word Problem for Groups and First Order Logic
I am trying to derive the undecidability of the Word Problem for an arbitrary group, let's call this Problem $WP(G)$.
It is clear to me that FOL and higher are undecidable and I want to reduce the $WP(...
- 407
3
votes
1
answer
86
views
Why is the post correspondence problem undecidable?
The post correspondence problem is, to my understanding, given two ordered collections of strings with the same cardinality, i.e., $\{t_1, t_2, \dots, t_n\}$ and $\{w_1, w_2, \dots, w_n\}$, does there ...
- 6,540
3
votes
0
answers
32
views
HexLife: Turing complete?
Has anything "interesting" been discovered if one generalizes Conway's Life
on a rectangular grid to a hexagonal grid?
There have been several explorations of Life on a hexagonal grid.
In ...
- 29.3k
0
votes
1
answer
204
views
Prove that there's no decidable language that separates two other languages.
I was reviewing for an exam and I found this question:
Let A and B be two disjoint languages (that is, A ∩ B = ∅). Say that a language C separates A
and B iff A ⊆ C and B ⊆ (not C) .
Define two ...
user1052197
0
votes
0
answers
12
views
Reference for strengthening of Church's theorem on undecidability of predicate calculus
I need a reference (it can be either a book or a published paper in English) for the following result: "Let $L$ be a language containing a 2-ary predicate symbol, then the set of all logically ...
- 414
0
votes
0
answers
18
views
How to prove a turing machine is decidable which accepts ⟨A, B⟩ | A and B are NFAs and L(A) ⊆ L(B).
So I'm trying to construct a Turing machine M = = {⟨A, B⟩ | A and B are NFAs and L(A) ⊆ L(B)}. I was wondering how to approach this problem as there are total 4 possibilities -
A accepts A
B accepts ...
0
votes
0
answers
32
views
What Are the Smallest Totally Ordered Set and the Conditional Valuation Rule Needed for Intuitionistic Countermodels for Propositions in IPC?
According to the Wikipedia article on Heyting algebras:
Every totally ordered set that has a least element 0 and a greatest element 1 is a Heyting algebra (if viewed as a lattice). In this case p→q ...
- 103
1
vote
0
answers
40
views
Whether an FO(PFP) formula is totally defined is undecidable?
How can I show that the problem that : Whether an FO(PFP) formula is totally defined is not decidable?
I have these:
PFP-formula: partial fixed point formula.
A formula is totally defined if for all ...
- 268
0
votes
1
answer
62
views
Are there any problems outside of the arithmatical hierarchy?
Do there exist problems that are outside of any level of the arithmetical hierarchy(as in even outside arbitrarily large ordinal levels?) But are in ALL. In other words, does AH = ALL?(where AH is all ...
- 71
0
votes
0
answers
33
views
How do i prove that HALT TM is undecidable with Diagonalization?
I am currently struggling with Theory of Computation Diagonalization topic, we are supposed to prepare for the test and one of the exercises I found is to prove that HALT TM is undecidable via ...
0
votes
1
answer
35
views
Definable classes of sentences despite Tarksi's Theorem
In number theory, I know that Tarski's Theorem rules out the possibility of the existence of a predicate which is true precisely for the Godel numbers of sentences which are true. However, do there ...
- 639
1
vote
0
answers
34
views
Quantifier elimination for non-polynomial functions
I lack much of the theoretical background for QE (my background is primarily optimization and control), but have stumbled across it in the process of learning about hybrid automata & decidability. ...
- 48
4
votes
1
answer
102
views
Tietze transformations and the trivial group
Suppose you have a finite presentation of a group and you want to determine if it yields the trivial group. We know this is unsolvable in general. But say you start from the trivial group and “...
- 207
0
votes
0
answers
63
views
Are there any statements that are n-undecidable for all n?
I understand that in a sufficiently complicated, consistent formal system, not all statements are true, not all statements are decidable, not all statements' decidability is decidable, 3-decidable, ......
- 1,230
2
votes
1
answer
69
views
Is it decidable if a finite set of equations have only trivial models?
Fix an algebraic signature $\Omega$. Let $F$ be a finite set of equations in $\Omega$. Is it decidable if the set $F$ has only trivial models? By trivial models, I mean one-element models. For example,...
- 13.3k
2
votes
1
answer
96
views
Show that $B$ is decidable
Let $A$ and $B$ be semi decidable languages. Moreover, $A \cup B$ and $A \cap B$ are decidable. I want to show that $B$ is decidable.
Firstly, I would like to know if the following approach works:
...
- 167
3
votes
0
answers
87
views
Can membership in a well-defined set be undecidable?
Finding out whether a proposition variable $A$,
its negation ${\sim}A$ or neither can be deduced from an infinite set of premises $\mathcal T$
(i.e. respectively $\mathcal T \vdash A$, $\mathcal T \...
- 256
0
votes
0
answers
31
views
1. Given a Turing Machine T , are there any input strings on which T loops forever? 2. Given a Turing Machine T and a string w, does T reject input w?
Given a Turing Machine T , are there any input strings on which T loops forever?
Given a Turing Machine T and a string w, does T reject input w?
How to prove the above two question's decidabiltiy , I ...
0
votes
1
answer
39
views
Satisfiability of Second-Order Logic: Is this Decision Problem Complete for Some Level of the Arithmetical Hierarchy?
Consider the following decision problem defined in terms of input/output:
Input: a second order logic [1] theory $\mathcal{T}$ (i.e., $\mathcal{T}$ is a set of second order logic formulas)
Output: ...
1
vote
0
answers
52
views
Show a theory $\Theta$ is complete.
I'm taking a introduction to Logic course and came across the following result:
Let $\Theta$ be a theory over a decidable signature $\Sigma$. Assume $\Theta$ has quantifier elimination and $F_0=\...
- 317
2
votes
2
answers
71
views
The range of a non-computable function that grows faster than computable functions is undecidable
Let $f$ be a non-computable function that grows faster than every computable function. I have to prove that $R=\text{Range}(f)$ is non-decidable.
I'm trying to prove the statement by contradiction. ...
- 331
0
votes
0
answers
20
views
Integer Division in Presberger Arithmetic?
Using the signature of the first order theory of Presberger Arithmetic (0, S , +), is it possible to write the function f(x) = [x/2] (where [.] is greatest integer function) as a function in ...
- 2,100
2
votes
1
answer
73
views
How to show that if there's a mapping reduction from L to its complement, it doesn't imply that L∈R?
I have the following prove/disprove claim:
if $$L\leq_m L^{c}$$ then $$L\in R$$
I figured out that I can theoretically provide a counter-example where both $$L,L^{c}\not\in(RE\cup co-RE)$$ but ...
0
votes
0
answers
13
views
Computer Algebra: How to find out when symbolic equality is decideable?
Richardson's theorem states that for a specific class of expressions $R$, $E \in R$,
$E = 0$ is undecideable.
This implies (To my understanding) that it is impossible to write a CAS that can solve all
...
- 1
14
votes
1
answer
168
views
Are the algebraic real numbers an automatic structure?
In the 1950's, Julius Büchi showed that $(\mathbb{N},S,+,0)$ is not merely a decidable structure as Presburger had shown, but an automatic structure, i.e. there is an encoding of the natural numbers (...
- 9,229
0
votes
2
answers
63
views
Is the decidability of all possible axiomatizations equivalent to decidability?
Introduction
This is a weird take on a few different topics in logic, so bear with me.
To frame this question, consider that "axiomatization" is to "theory" as "...
- 3,707
2
votes
0
answers
59
views
Using diagonalization approach, how to show the existence of at least one set of natural numbers that is not computable?
I have studied the halting problem and the concepts of decidability and computability, however, I am stuck with the transfer of Turing machines to sets of natural numbers. Specifically, using the ...
- 121
2
votes
1
answer
142
views
Why is Q (Robinson arithmetic) both undecidable and axiomatizable?
I'm studying computability and its terminology is very confusing. So, Q (Robinson arithmetic) is undecidable AND axiomatizable, right?
But if axiomatizable means that the collection of Q theorems is ...
- 33
0
votes
1
answer
53
views
Help me understand decidability of an axiom system of a theory
The author of the book I'm reading defined an axiom system $X$ of a theory $T$ like this:
Let $X$ be a set of formulas. Then $X$ is an axiom system of a theory
$T$ of which it holds that $T = \{ \...
- 1,815
0
votes
0
answers
74
views
Multitape Turing Machine - Check input's primality
I've got this homework for next tomorrow and unfortunatelly I have no idea how to design this machine.
Requirement: Build a 2-tapes Turing Machine, which has a number as input a natural number (unary ...
- 1
3
votes
1
answer
110
views
Proof that the Post Correspondence Problem is undecidable
The lecture of MIT professor Michael Sipser, available here and his book Introduction to the Theory of Computation, Third Edition, chapter 5, both contain essentially the same proof that there can be ...
- 396
0
votes
0
answers
21
views
Languages consisting of set of descriptions of Turing machines - recognizable, decidable?
Sipser's Introduction to the Theory of Computation, Third Edition, chapter 3, Problem 3.14, asks:
"Let $B=\{<M_1>,<M_2>,...\}$ be a Turing-recognizable language consisting of TM ...
- 396
1
vote
1
answer
740
views
Every infinite Turing-recognizable language has an infinite decidable subset
Sipser's Theory of Computation, Third edition, chapter three asks me to prove this.
I see three languages in this problem:
The original recognized language
The set of strings in which the original ...
- 396
0
votes
1
answer
53
views
Simple concrete example of a language that is Turing recognizable but not decidable
Sipser's Theory of Computation, third edition, chapter three introduces the idea that such languages exist but gives no examples. Chapter four gives examples in terms of abstract languages whose ...
- 396
0
votes
3
answers
127
views
Why does Alan Turing proof of the halting problem is considered a proof that mathematics is undecidable?
Whenever I read about the Entsheidungsproblem or the halting problem, I read that this proof proves that there is no general algorithm to solve this problem for any given algorithm with a given input. ...
- 31
0
votes
2
answers
72
views
Show the projection of decidable language is Turing-recognizable
Sipser's text on theory of computation, second edition, exercise 4.17, contains the following exercise:
"Show C is Turing-recognizable if and only if there is a decidable language D where
$C=\{x|\...
- 396
0
votes
2
answers
40
views
Is this modified characteristic function computable?
Let $P(n,k)$ be decidable and define
$$f(n)=\begin{cases}1&\text{if there are exactly two }k\text{ with }P(n,k),\\
\text{undefined}&\text{otherwise}.\end{cases}$$
I wonder if this function is ...
- 4,397
0
votes
1
answer
137
views
Prove that recursively enumerable languages are not closed under set difference
So I need to prove that the difference between two recursively enumerable (RE) languages $A$ and $B$, $A - B$, is in general not RE. I know that RE languages are not closed when it comes to the ...
- 355
0
votes
2
answers
42
views
Must every Turing-complete language be able to enumerate precisely those algorithms which return a particular value?
This kind of enumeration is particularly easy with some languages. For example, using SKI combinators, start with the expression $\mathbf{SKK}$ (Church encoding for $1$) and systematically apply the ...
- 4,941
0
votes
0
answers
45
views
Reduction of RE and REC languages
Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.
And also I know that if $...
- 1
1
vote
1
answer
400
views
Why is "Turing machine makes no left move" decidable?
We know that every RE language is accepted by Turing machine. And emptiness, finiteness of every RE language is undecidable. My question is how I check decidability "the Turing machine makes move ...
- 1
1
vote
2
answers
158
views
Decidability of DCFL and Undecidability of CFL with respect to regularity
I synced with this Hendrik Jan's answer that to prove undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and ...
user976798
0
votes
1
answer
162
views
Bijection between $2^{\Sigma^*}$ and $\mathbb R$
Is there a Bijection in between $2^{\Sigma^*}$ and $\mathbb R$? Here $2^{\Sigma^*}$ denotes the set of all languages over a finite alphabet.
If I have an uncountable set, then its powerset will also ...
user976798
1
vote
0
answers
52
views
What background do I need to know to understand the paper published by Alan Turing mentioning the halting problem?
I am interested in understanding the proof that mentioned that the halting problem is an undecidable problem from the original paper of Alan Turing's called "ON COMPUTABLE NUMBERS, WITH AN ...
- 31
0
votes
0
answers
43
views
Conversion NPH problem reduction
To prove any problem $R$ is NPH then take any known NPH problem $L$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $L$, then prepare another instance ...
user974277
0
votes
1
answer
40
views
Could the decidability of a theorem be undecidable?
Given some theorem $T$, could the question "is $T$ decidable?" be undecidable?
I assume the answer is yes, and if it is, could the decidability of a theorem be undecidable even if the ...
- 1,474
5
votes
1
answer
133
views
Essential undecidability of binary string arithmetic
The weak theory of concatenation of binary strings is essentially undecidable.1 Is Presburger arithmetic with two successors (one for each letter) essentially undecidable? Formally, consider the ...
- 5,060
1
vote
1
answer
330
views
Why is "decidable" included in "Turing-recognizable"?
(pic from "introduction to the theory of computation" - Michael Sipser)
According to my understanding:
Turing-recognizable languages are languages whice are accepted by a Turing machine;
...
- 113
0
votes
0
answers
50
views
Is every axiomatizable theory $T$ countable?
These are the definitions I'll be working with. (Note that they are informal and the author promises more formal ones later on in the book, but I'm not there yet.)
A set $Z$ of strings of a given ...
- 1,815
1
vote
0
answers
67
views
Transcendental numbers are decidable: a proof?
My opinion is that the statement, for a real number $X$:
"$X$ is transcendental."
is decidable.
The sketch of the "proof" should be the following.
If transcendency or algebraicity ...
- 1,266