# 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
Filter by
Sorted by
Tagged with
24 views

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 ...
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  theory $\mathcal{T}$ (i.e., $\mathcal{T}$ is a set of second order logic formulas) Output: ...
1 vote
52 views

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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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. ...
72 views

1 vote
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 vote
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 ... 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 ... 1 vote
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 ...
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 ... 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 ...
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 ...
1 vote
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; ...
### 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 ...
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 ...