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
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(...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
  • 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 “...
user avatar
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, ......
user avatar
  • 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,...
user avatar
  • 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: ...
user avatar
  • 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 \...
user avatar
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 ...
user avatar
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: ...
user avatar
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=\...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
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 "...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 = \{ \...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
  • 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|\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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; ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5