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

learn more… | top users | synonyms

7
votes
2answers
65 views

Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from ...
1
vote
1answer
61 views

TM that accepts all strings is recognizable or not?

Lets say we have the following language $L = \{\text{$M$ is a TM such that $M$ accepts all strings}\}$, is this recognizable or not? I have a feeling it is unrecognizable, if this statement is correct ...
0
votes
1answer
57 views

How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

Let a language A = {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}. How can I prove that this is undecidable? I have considered trying to build the ATM ...
1
vote
1answer
34 views

Example of a simple recognizable language, whose complement is not recognizable

Can any one provide me with a simple language that is recognizable, but that it's complement is not? I have read that recognizable languages may have this property but I am yet to find an example to ...
1
vote
1answer
51 views

Is converting an ambiguous grammar to an unambiguous grammar computable?

Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).
7
votes
1answer
49 views

Problem complete for the class of ALL languages

$\text{ALL}$ is literally the class of ALL languages. Are there $\text{ALL}$—complete problems? That is, are there problems for which a solution would allow one to solve any problem whatsoever? ...
0
votes
0answers
26 views

How to show if the following function isn't computable?

Given a $\Gamma = \{0,1, \square\}$ and an function $f(n)$ which calculates the maximum number of steps from a turing-machine, with $n$ states and which holds on an empty tape. How to show that the ...
1
vote
1answer
42 views

Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs

I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of ...
0
votes
1answer
70 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 $\overline{\mathcal{...
1
vote
2answers
49 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
2answers
142 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 ...
4
votes
1answer
133 views

Prove that there is no computable enumeration of all decidable languages

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 ...
3
votes
1answer
120 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
169 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
62 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
50 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
39 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
27 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
64 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
104 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
52 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
66 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
51 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) = L(...
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
148 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
282 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
796 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
129 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
40 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
49 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
80 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
94 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
141 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 this:...
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
138 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
86 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
72 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 ...
6
votes
2answers
158 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
361 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
118 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 $L\...
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
50 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 $\...
1
vote
1answer
87 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
48 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
35 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
128 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 ...