Questions tagged [undecidability]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
19 views

Are run time bounds in P decidable when the problem is promised that an input program must halt?

I'm solving Problem 11-10(b) in "what can be computed". 11.10 Consider the decision problem HALTSINSOMEPOLY (HISP), defined as follows. The input is a program P, and the solution is “yes” ...
0
votes
0answers
41 views

Is the language of Turing Machine encodings decidable is this instance?

I have an exercise question as follows: L is a set of all Turing Machine encodings for which the Turing Machine halts after a number of steps less than or equal to the minimum value among |w| and 1000,...
0
votes
1answer
76 views

A question on decidability

I have a homework question that is as follows: L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P ...
0
votes
0answers
24 views

Would a “TM starting with a blank tape will ever write a nonblank symbol anywhere before halting” be decidable?

Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?
0
votes
1answer
20 views

Please help me understand this proof of the undecidability of “Do two halting Turing machines accept the same language?”

Do two halting Turing machines accept the same language? Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"): Let M be an arbitrary Turing machine. Let ...
0
votes
0answers
11 views

Is the halting problem decidable for TMs that do not write to the tape? [duplicate]

Is the halting problem decidable for TMs that do not write to the tape? Once a read only tape TM repeats a configuration, it will loop forever. Therefore, all we have to do to decide the above is ...
1
vote
1answer
16 views

Complement of equality problem of Turing machine is recognisable or not

Complement of equality problem of Turing machines is unrecognisable or not-recognizable but How?. As per my knowledge it is recognisable if you can decide its accept condition but not Reject and ...
-2
votes
0answers
43 views

Can $A_{TM}$ be mapping reduced to an unrecognizable language?

$A_{TM}$ is the language of pairs of ⟨M,w⟩ such that M is a TM that accepts w Can the language $A_{TM}$ be mapping reduced to an unrecognizable language? In other words, $A_{TM} \leq_m L$, and L is ...
0
votes
0answers
12 views

Purpose of Acceptance Problem

I am confused about the purpose/statement of the Acceptance problem: $A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$ It can be shown that $A_{TM}$ is uncomputable, so we know that, ...
0
votes
1answer
22 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
1
vote
1answer
26 views

Proving Undecidability with reductions - Why do some proofs not use an Oracle?

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf So as I've learnt it, say we want to prove a new Language L is ...
1
vote
2answers
63 views

Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have ...
-2
votes
1answer
18 views

$\{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?

How can we show that the language $K = \{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?
-1
votes
1answer
15 views

If $ \text{NV}_{\text{TM}}$ is decidable, then $A_{TM}$ is decidable?

It seems that $ \text{NV}_{\text{TM}} = \{〈N〉: N \text{ a Turing-Machine and } L(N) ≠ ∅\}$ is not decidable. Here is a proof: Suppose that $\text{NV}_{\text{TM}}$ is decidable with the Turing-Machine ...
0
votes
2answers
30 views

Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$ We have to show that $C$ is unrecognizable. I am having trouble going on about ...
1
vote
0answers
43 views

Undecidability of an Intersection

1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable? 2)What if we replace L with the complement of L? Either 1 or 2 is decidable and the other ...
0
votes
1answer
30 views

Decidability of languages with dfa/turing-machines

For any alphabet and any natural number k, a language of strings at least k is decidable. So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has ...
0
votes
1answer
69 views

How to prove (un)decidability

Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
-2
votes
0answers
8 views

Is the following language decidable and/or recursively enumerable? Input: A Turing Machine M. Question: Is |L(M)| ≤ 1?

Want to know whether the following language is decidable and/or recursively enumerable: Input: A Turing Machine M. Question: Is |L(M)| ≤ 1?
1
vote
1answer
24 views

Join of recursively enumerable set and its complement

The union of a recursively enumerable set and its complement is $\Sigma^*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$? $$ \{ \# ...
-1
votes
1answer
18 views

Show that a language is not decidable by reducing from ATM

Let (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) show that the language L={<M1,M2,w> | M1 and M2 both accept or reject w} is undecidable by reducing ATM ...
2
votes
1answer
18 views

Are there decidable non-trivial properties of a LBA's accepted language?

The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable? Given a LBA, can you decide whether there exists an input ...
3
votes
1answer
92 views

Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?

Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite. By leveraging this oracle, can I solve the halting problem? That is, on an ...
0
votes
0answers
37 views

A language is decidable iff some enumerator enumerates it in decreasing order [duplicate]

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. What does it mean by enumerator enumerating in decreasing order? I am so confused about this concept....
1
vote
1answer
75 views

Show that a language is decidable iff some enumerator enumerates the language in decreasing order

Show that a language is decidable iff some enumerator enumerates the language in decreasing order. I know a language is decidable iff some enumerator enumerates the language in the standard string ...
0
votes
1answer
36 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
-3
votes
2answers
65 views

Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
1
vote
2answers
61 views

Are there 3-colorable maps that can never be colored?

I just watched this explanation of zero-knowledge proofs with Avi Wigderson: https://www.youtube.com/watch?v=5ovdoxnfFV Key claims from the video: Every formal statement can be translated into a map ...
1
vote
2answers
43 views

Turing machine that checks whether a given string is an output of a given machine and input

Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$? My ...
0
votes
1answer
35 views

Deteremine if Language is in $R$ or $RE$

$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$ Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$. My ...
0
votes
0answers
38 views

halting problem vs watchdog

I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
3
votes
1answer
60 views

Characterization of computationally universal functions

Is it correct to state that $u$ is a universal function if and only if $$ \forall f : \text{RE} \quad \exists g : \text{R} \quad \exists h : \text{R} \quad f = h \circ u \circ g $$ where RE is the set ...
1
vote
1answer
38 views

A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)

I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'): ...
-3
votes
1answer
30 views

Decidability of whether $w \in L(M_1) \setminus L(M_2)$

I'm studying for my finals and I came across this question from past exams: Is the following language decidable? $$ L = \{ \langle M_1,M_2,w \rangle \mid w \in L(M_1) \setminus L(M_2) \}. $$ How can ...
2
votes
2answers
171 views

Proving decidability

Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting ...
1
vote
1answer
38 views

Is there a connection between the Undecidability Theorem and “software complexity”?

I was reading Complexity: The Emerging Science at the Edge of Order and Chaos and a certain passage got me really intrigued. When discussing Chris Langton's explorations of artificial life algorithms,...
0
votes
1answer
329 views

Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?
2
votes
2answers
205 views

Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
0
votes
1answer
49 views

Understanding the union of an undecidable language with a finite or decidable language

I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable. This is confusing me because if $L$ were to be a semi-...
0
votes
2answers
74 views

Decidability of Turing machines and misconceptions on the halting problem

In an online discussion on Turing machines and decidability recently, I blatantly theorized that any problem about a specific single Turing machine must be decidable, the question of undecidability ...
0
votes
1answer
69 views

How this language belong to R?

Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \}$$ I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
2
votes
1answer
67 views

What is the actual scope of the Halting Problem impossibility result?

Consider the Halting problem : No TM H exists which given any TM and input, decides whether that TM will halt on that input. The usual proof (informally) is that if such an H existed, then a function ...
0
votes
1answer
45 views

Is the decision problem, for a Turing Machine are there any input strings rejected decidable?

Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it. ...
0
votes
0answers
40 views

Let $f$ be a computable and injective function. Is $f^{-1}$ computable and injective?

So I just started learning about computability, undecidability and Turing machines. And I wonder if: Given a computable and injective function $f$, is $f^{-1}$ also computable and injective? I don't ...
0
votes
2answers
41 views

Is it decidable when a TM M gets another as inputs and checks if it fullfiills certain property?

I was asking myself if it is not possible to decide the language where a TM M gets the Godel number of a TM M' as input and the checks if, let us say, the TM M' has a certain amount of transitions. My ...
0
votes
1answer
225 views

Determine if a language is Decidable or semi decidable

Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$. We need to determine, without ...
0
votes
0answers
41 views

Show that this language is undecidable

Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$ I would like to know if ...
1
vote
1answer
24 views

Does there exist a undecidable infinite language with only a finite undecidable subset?

I know that there's no such thing as a finitely sized undecidable language. However, does there exist an undecidable language where a finitely sized set of undecidable elements are 'hiding among' an ...
0
votes
0answers
182 views

reduction from ALLTM to ETM

I am trying to understand why this "proof" of ETM undecidability is wrong. ALLTM={ < M >|M is a TM, L(M)=∑*} ETM={< M >|M is a TM, L(M)=∅} We know that ALLTM is undecidable, lets ...
3
votes
1answer
118 views

Deciding whether complement of context-free language is context-free

I need to find out if the following problem is decidable: Given a context-free language $L$, decide whether its complement $\bar{L}$ is also a context-free language. I am having trouble in defining ...

1
2 3 4 5
16