Questions about problems which cannot be solved by any Turing machine.

learn more… | top users | synonyms

-4
votes
0answers
17 views

Is a union of any TM language and the halting problem language decidable [duplicate]

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
0
votes
1answer
56 views

Classify the set of all TMs whose languages from the accepting problem

Let $$L = \{ \langle M \rangle \mid M \text{ is a Turing machine so } A_{TM} \leq_m L(M) \}$$ The question is whether $L$ is in $\mathcal{R}, \mathcal{RE}, co-\mathcal{RE}$ or in ...
1
vote
2answers
36 views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
0
votes
1answer
106 views

Decidability of the TM's computing a none empty subset of total functions

I have this HW problem: Let $F$ be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote $$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function ...
2
votes
1answer
80 views
+50

a theorem about the enumeration of R and a subset of always halting TMs

The question: Let $L_1,L_2,...$ be an enumeration of $\mathcal{R}$ and define $A_i = \{\langle M\rangle \ | \ L(M) = L_i\}$. Let $L$ be a language in $\mathcal{RE}$ such that $L \subset \{\langle ...
0
votes
0answers
41 views

Is ATM with decidable TM also undecidable? [closed]

Is ATM with decidable TM also undecidable ? We can tell the UTM to go to reject state if it sees a reject state from TM so it can be decidable. $$ATM = \{\langle M, w \rangle \mid \text{\(M\) is a ...
3
votes
1answer
110 views

Undecidable vs Unsolvable?

In decidability theory, I understand that if a problem is labeled "decidable", then we can construct a Turing Machine that definitively tells us whether an input is valid or invalid. My question is ...
1
vote
2answers
152 views

Is it possible to design a programming task that is unsolvable?

Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least ...
3
votes
1answer
57 views

Undecidability of REGULAR_TM (Detail within Proof)

I'm reading through Sipser's Intro to the Theory of Computation for a class, and I'm having trouble understanding one of the examples in the book. The example shows how $REGULAR_{TM}$, defined as the ...
2
votes
2answers
61 views

Language of TMs such that one state is visited most often

To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset ...
1
vote
0answers
46 views

Language of Turing machines that never visit some given state

Can someone help me to determine and prove if the following language is decidable or not? I tried to think on some reductions but I can't figure it out... $$A=\{\langle M\rangle|\text{$M$ is $TM$ ...
1
vote
2answers
35 views

The language of Turing machines that accept exactly $k$ inputs

For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts. Is $X_k$ ...
0
votes
1answer
26 views

Decidablity with exponential number of solution

I am trying to understanding this. If a problem has exponential amount of candidate solutions, such as 2^2^n. Is this decidable? To my understanding, as long as its' verfiable, no matter how big the ...
0
votes
1answer
63 views

Is this decidable language a subset of this undecidable language?

I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples. A(DFA) = {(M, w): M is a deterministic finite automaton that accepts ...
0
votes
1answer
98 views

Prove whether this problem is decidable or undecidable [duplicate]

So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state. I convinced ...
7
votes
2answers
1k views

Is it possible that the halting problem is solvable for all input except the machine's code?

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help. Is it possible that the halting problem is decidable for any TM on any ...
2
votes
1answer
51 views

Recursively enumerable but non recursive subset of an infinte recursive language

How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive? I think we need to show there's a list of natural numbers that can't be ...
1
vote
1answer
57 views

context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem is L finite or infinite? is undecidable. where was this 1st proved/ published? are there any cases in the literature of ...
3
votes
1answer
48 views

Decidability of equivalence problem with limit

I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable. If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = ...
4
votes
1answer
57 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
0
votes
0answers
146 views

Trying to show if two languages are recognizable or not

I have two languages that I am trying to prove are recognizable or not: Let L1 = {<\M, w> : M is a Turing machine that accepts string w and does not accept string ε}. Is L1 recognizable? Prove ...
4
votes
3answers
280 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
7
votes
3answers
792 views

Undecidability of telling if a program returns true or false

Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are ...
8
votes
3answers
128 views

Constructive version of decidability?

Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). ...
3
votes
1answer
39 views

Linear Bounded Automaton that accepts all strings

I'm currently reading Sipser's Introduction to the Theory of Computation, and I'm reading up about linear bounded automata, now we know from Rice's Theorem that whether a TM can accept all strings in ...
4
votes
1answer
43 views

Solving systems of linear equations over semirings

So I have come across an issue where it would be very nice to solve systems of linear equations over semirings but I have no clue how to do that. Over a field I would use Gaussian elimination but I'm ...
1
vote
1answer
76 views

Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$ I have to prove that this is not R.E. and not co-R.E. I know how to approach these kind of problems. For ...
0
votes
1answer
78 views

ETM Undecidability

I'm having trouble convincing myself of the proof for the following theorem: ETM = { <M> | M is a TM and L(M) = ∅} is undecidable. I think I understand ...
-2
votes
1answer
35 views

Undecidability of language [duplicate]

I'm trying to show the language $L=\{\langle M\rangle: M$ is a Turing Machine with runtime $O(n)\}$ is undecidable. I've been trying to reduce the Halting problem $H_{alt}$ to $L$, but I'm unsure of ...
5
votes
2answers
136 views

Decidability of dependent typing on primitive recursive languages

With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is ...
4
votes
1answer
102 views

Proving a certain superset the halting language is not recursive

Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w ...
2
votes
1answer
92 views

Showing undecidability

I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...
-1
votes
1answer
85 views

Language is decidable or not? [closed]

Prove each languages decidable or undecidable. { <M> | L(M) is not recognizable} I am not able to understand how this works. And what is recognizable ...
-1
votes
2answers
67 views

Is the following language decidable, enumerable or non-enumerable?

$$L = \{\langle M_1 \rangle, \langle M_2 \rangle \mid \text{\(M_1\) and \(M_2\) are TMs and \(\forall X, M_1(X) = M_2(X)\)}\}$$ Is this language decidable, enumerable, or non-enumerable? And in ...
3
votes
2answers
93 views

Is it decidable whether a given context free grammar generates an infinite number of strings?

Is the decision problem "Does a given context free grammar generate an infinite number of strings" decidable? In order to test whether a context free grammar generates an infinite number of strings or ...
4
votes
1answer
343 views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither ...
3
votes
1answer
60 views

Is the following language recursively enumerable?

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$. I would like to prove that $L\notin RE$. I can show that $\overline{L}\notin RE $ that is ...
1
vote
0answers
26 views

Reduction of decidable and undecidable problems [closed]

Let: f be a decidable decision problem. g be an undecidable decision problem. I refered to those rules: If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable. If $f$ ...
4
votes
1answer
45 views

How to prove the following language is not in R

Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps ...
0
votes
1answer
33 views

Reduction from $A_{TM}$ to Rice theorem: what if input of $A_{TM}$ loops? [on hold]

I'm learning this reduction from $A_{TM}$ to $R_P$ for the proof of Rice's theorem. This is the reduction: https://gyazo.com/10cdc3b833a8d1bd9cdbb1eb08e76303 (Source of the slides: The University of ...
1
vote
1answer
82 views

two languages reducible to each other can belong to RE and recursive?

If two languages L1 and L2 both are reducible to each other in polynomial time then which of the following is false? A L1 is decidable and L2 is undecidable. B L1 is recursive and l2 is RE C ...
1
vote
0answers
16 views

Computing shifted fix point in the BSS model

Let $p \colon \mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$ be a one-dimensional function that fulfills $p(0)=0$. Moreover, we are given some value $u \in \mathbb{R}_{> 0}$ such that $p$ is ...
1
vote
2answers
47 views

Undecidable language and Turing Machines

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ...
2
votes
0answers
34 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
1
vote
2answers
65 views

Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input. Here's the copy-paste of that ...
8
votes
1answer
222 views

Problems whose decidability status is unknown but known to be less hard than the halting problem

Are there problems the decidability of which is unknown but it is known for certain that the problems are less hard than the halting problem.
24
votes
2answers
406 views

Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Every undecidable problem that I know of falls into one of the following categories: Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the ...
1
vote
1answer
86 views

A question on encoding

Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this ...
-2
votes
1answer
65 views

Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable [closed]

$$L = \{\langle M,w\rangle \mid \text{\(M\) accepts \(w\) only}\}$$ How can I prove this language is unacceptable (unrecognisable)? I think I should use a reduction, I'm not sure how.
5
votes
2answers
125 views

Will encoding affect computability?

I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the ...