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

learn more… | top users | synonyms

6
votes
1answer
54 views

Is Post's Correspondence Problem decidable with fixed word size?

So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$. I'm wondering, can anything similar be said for when there is a fixed word length? To be precise, here's ...
3
votes
1answer
34 views

Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that ...
-2
votes
0answers
29 views

Why is it not decidable if a TM writes a given symbol?

The problem Does a TM M on input w ever writes a particular symbol on its tape? is undecidable but we can always check if the TM ever writes that particular symbol on the tape when input string ...
-1
votes
0answers
42 views

Solvable & Unsolvable Problem Detection [duplicate]

be aware that this problem dosnt have solution. I ran into A multiple choice question on previous midterm on Computation Theory course. this question is which of the following problem is not ...
1
vote
2answers
57 views

Can an intersection of two context-free languages be an undecidable language?

I'm trying to prove that $\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language. I know that context-free languages are not closed ...
3
votes
1answer
52 views

The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

Can the following two statistics be bounded: the proportion of halting programs vs non-halting programs the proportion of decidable vs undecidable languages For example, can we say that one class ...
1
vote
1answer
28 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
0
votes
1answer
48 views

Why is $A_{TM}$ reducible to $HALT_{TM}$?

In Sipser, there is a proof I don't understand. First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input. ...
0
votes
1answer
27 views

Intersection and partial quantity decidability [closed]

I'm still insecure in the section decidability (no proof needed, I want to divine it): X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable? X is decidable ...
3
votes
3answers
144 views

Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]

Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
2
votes
1answer
29 views

Why can't configuration counting decide undecideable problems?

I know it might sound like a silly question, I just can't get my head around it... I just read that $DSPACE(f(n))\subseteq DTIME(n\cdot 2^{O(f(n))})$. The proof for it relies heavily on the fact ...
1
vote
2answers
65 views

if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?

Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter ...
3
votes
1answer
93 views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
1
vote
2answers
61 views

Do all decidable problems lie in the class NP?

All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a ...
1
vote
1answer
72 views

Turing Decidable [closed]

M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where Q ={q1, q2, qaccept, qreject}, Σ = {0, 1}, Γ = {0, 1, U}, and transition function δ is as follows: ...
1
vote
0answers
21 views

Undecidability instance on a “find a proof/disproof” machine

I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on: Suppose we built the ...
0
votes
0answers
43 views

Can we recognize wheter a Turing machine is a decider?

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor ...
0
votes
2answers
47 views

Reducing A(TM) to some decidable problem

We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable? I couldn't find an example or theory. Thanks
1
vote
0answers
29 views

Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
0
votes
1answer
42 views

How can a problem be undecidable yet enumerable? [duplicate]

How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers ...
0
votes
1answer
32 views

How can an LBA check legality of TM transitions without extra memory?

In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$. The reduction is proposed in the following manner: we receive a TM $M$ and a ...
2
votes
1answer
96 views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
1
vote
0answers
17 views

Is deciding whether there is a non-constant solution to a functional inequality with polynomial arguments decidable, with 2 variables?

So suppose we have a functional inequality with polynomial arguments in $2$ variables, $\sum_i c_i f(p_i(x,y)) \geq 0$, where $c_i$ are say given integer constants and $p_i$ are given polynomials, say ...
6
votes
2answers
80 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
1
vote
1answer
32 views

How do you prove that this TM decides a language that is undecidable? [closed]

In Sipser's Introduction to the Theory of Computation, there is an exercise that asks to prove $T$ decides $A_{TM}$, which is the language $$A_{TM} = \{ \langle M,w \rangle | M \text{ is a TM and $w ...
1
vote
1answer
42 views

Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
5
votes
2answers
290 views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
0
votes
1answer
93 views

how do I find a undecidable subset of a set that's decidable? [closed]

Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?
0
votes
0answers
11 views

two undecidable languages with a decidable union/intersection? [duplicate]

does there exist two undecidable languages such that their union is decidable? what about a decidable intersection? One thing that I've been trying to figure out is if J and K are both undecidable ...
4
votes
2answers
469 views

Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...
4
votes
2answers
134 views

Is this language depending on P = NP recursive?

Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language $$L = \begin{cases} (0+1)^* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$ ...
0
votes
1answer
46 views

Palindromes and linear grammars

Given a linear grammar G, is it possible to determine if L(G) contains a palindrome?
2
votes
1answer
60 views

Undecidability and Countability

This question is prompted by Undecidable unary languages (also known as Tally languages) How does the countability of a language imply (un)decidability?
2
votes
2answers
91 views

Is equivalence of CFGs decidable for finite sets of grammars?

Is there a way to show that for all finite sets $S$ of context free grammars, there exists a Turing Machine $M$ such that for all grammars $G_1, G_2 \in S$, we have that $M(G1,G2)$ terminates and ...
1
vote
1answer
114 views

Reduction to complement of Accept Problem

I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \}$$ To this Turing ...
1
vote
3answers
160 views

Determining if a context-free grammar produces even-length strings [closed]

Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?
1
vote
1answer
70 views

Decidability of an regular expression

I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing. Be A = {(R)|R it ...
4
votes
1answer
97 views

Is it possible to prove EQTM is undecidable by the Rice theorem?

Given the problem $EQ_{TM} = \{ \langle M_1, M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice ...
0
votes
1answer
19 views

Decidability of fullness of intersection of a CSL with a regular language

Let $L_r$ be a regular language with alphabet $\Sigma$ and $L_{\text{csl}}$ be a context sensitive language. Are any of the following questions decidable? $L_r \cap L_\text{csl} \stackrel{?}{=} L_r$ ...
1
vote
1answer
72 views

Understanding a proof for the existance of a non-computable function

For school, we have a proof that some functions are not Turing computable. The example is: $$ G(k) = \begin{cases} f_k(k) + 1 & \text{ if $f_k(k)$ is defined}, \\ 1 & \text{ ...
1
vote
3answers
154 views

Is the image of a total, non-decreasing function decidable?

This is an exercise I've been struggling with for a while: Let $g : \mathbb{N} \to \mathbb{N}$ be a total, non-decreasing function, i.e. $\forall x > y.\ g(x) \geq g(y)$. Is the image $I_g$ of ...
0
votes
1answer
177 views

Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be: decidable (recursive) or undecidable (nonrecursively enumerable) ...
0
votes
1answer
37 views

Turing Machine 'marking' specific portion of encoding

Given a turing machine $T$ that receives an encoding of another turing machine and a word $<M><w>$, can $T$ 'run' through the encoding and 'mark' specific transitions/states? For example, ...
4
votes
1answer
163 views

Why is deciding regularity of a context-free language undecidable?

As I have studied, deciding regularity of context-free languages is undecidable. However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient ...
2
votes
2answers
614 views

Undecidable unary languages (also known as Tally languages)

An exercise that was in a past session is the following: Prove that there exists an undecidable subset of $\{1\}^*$ This exercise looks very strange to me, because I think that all subsets are ...
3
votes
1answer
46 views

Question about the undecidability of $A_{TM}$

You probably know this one (or at least a version of it). Let $P$ be a program code, and $w$ be an input string. Define $A_{TM}=\left\{(P,w)| P(w)=1\right\}$. Meaning: $A_{TM}$ is the set of all ...
0
votes
2answers
77 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$ is undecidable by giving an explicit mapping reduction. To show ...
-1
votes
3answers
254 views

Decidability of Turing Machines with input of fixed length [closed]

I'm learning about undecidability, and found this question: ...
0
votes
1answer
69 views

Can the complement of a non-recursive language be RE

I've got a problem where I need to check the validity (i.e to say whether it's true or false) of the following statement: Complement of a non-recursive language can NEVER be recognized by any ...
1
vote
1answer
81 views

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present. This is the reduction they give: ...