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

learn more… | top users | synonyms

-2
votes
1answer
67 views

Language is decidable or not?

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
60 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
50 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
151 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
37 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
18 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
38 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
13 views

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

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
49 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
15 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
39 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
28 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
49 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 ...
7
votes
1answer
212 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.
21
votes
2answers
372 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
85 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
57 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
120 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 ...
4
votes
1answer
60 views

Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable? I tried diagonalization but can only ...
-1
votes
1answer
52 views

How to make an undecidable Turing Machine decidable?

I came across the following question in my revision. I would like to know how to solve this and in general what are the techniques I can use to make an undecidable TM decidable by changing inputs? ...
1
vote
2answers
356 views

Is how much memory a program needs computable?

We know that how much time a program needs is not computable. Do we know how much memory a program needs is decidable?
0
votes
1answer
41 views

Understanding the proof of the halting problem [closed]

I came across the following example that proves that the blank tape halting problem is not decidable. I understand the proof technique, but I just don't see how the blank tape problem is shown to ...
0
votes
1answer
80 views

Are “TM M accepts some string of length greater than 100” and “TM M accepts some string of length at most 100” decidable?

I have two questions as in the title: TM M accepts some string of length greater than 100 TM M accepts some string of length at most 100 Since 1. is infinite, we can rephrase question as "does TM ...
8
votes
2answers
81 views

Decidability of checking an antiderivative?

Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether $$F(x) = \int G(x)dx.$$ Let's suppose that my functions are composed of elementary functions (polynomials, ...
2
votes
1answer
189 views

Halting problem without input?

I'm only a layman therefore only discuss stuff naïvely. I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able ...
0
votes
0answers
17 views

Show that the set of TMs that can write z is undecidable [duplicate]

I want to show that $\qquad L = \{\langle M \rangle \mid \text{TM $M$ will write a $z$ to the tape at some point for some input}\}$ is undecidable. I'm really not sure how to show this is ...
1
vote
1answer
69 views

Closure properties of undecidable languages

I know that the decidable are close under: complementation, union, intersection and concatenation? What about the undecidable languages? I think they are close under complementation, but not under ...
2
votes
0answers
49 views

How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...
4
votes
1answer
101 views

Prove REGULAR_TM is undecidable

I am studying the proof of the following theorem: Given the language $\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$ ...
0
votes
0answers
41 views

Turing machine M overwrites a non-blank char by B (Blank)?

What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'? Intention of the question: I am trying to answer how the halting ...
3
votes
3answers
85 views

Testing two DFAs generate the same language by trying all strings upto a certain length

Given the language $EQ_{dfa} =$ $\{<A, B> | A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$ Prove that $EQ_{dfa}$ is decidable by testing the two DFAs on all strings upto a certain size. ...
0
votes
0answers
22 views

Computability of $\{y: \text{for some $i$, Turing machine $M$ accepts $y^i$}\}$

Is the set $K = \{y: \text{for some $i$, Turing machine $M$ accepts $y^i$}\}$ decidable or computational enumerable? How to prove this? Attempt: We can write a program to compute $i$th root of ...
1
vote
1answer
79 views

Q: Is chess game movement TM decidable?

If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable? My ...
4
votes
1answer
71 views

Proving that a language is not Recursive

I have the following language: T = {M | there exists w such that M accepts w within |w| steps} I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove ...
1
vote
1answer
64 views

Non-computability and Undecidability?

Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?
3
votes
0answers
41 views

Given a TM $T$ does $T$ ever leave the initial state when start tape is blank?

I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution. Can someone help me out? ...
5
votes
1answer
191 views

Computational complexity of finding the roots of a polyomial

I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial ...
10
votes
3answers
779 views

undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
0
votes
0answers
23 views

Can we use Rice's theorem to prove that A_TM is undecidable? [duplicate]

I am confused as to whether what constitutes a valid property. My text states that "The domain of property P must be the set of SD languages". Now, $A_{TM} = \{ \langle M,s \rangle \, | \text{ M is ...
3
votes
3answers
310 views

Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case. EDIT If it can be reduced to Halting problem, then how? ...
1
vote
0answers
63 views

Undecidability of an existential theory

$F[u, u^{-1}]$ is a ring that contains the polynomials in $u$ and $u^{-1}$ with coefficients in the field $F$. Some theorems (from ...
1
vote
1answer
64 views

Problem in Papadimitriou's “Computational Complexity” seems odd

I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition. On page 66, we have: 3.4.1. Problem: For each of the following problems involving ...
-2
votes
1answer
71 views

Two Disjoint Turing-recognizable languages do not have a decidable language

Let languages $A, B$ be defined as $$\begin{align} A &= \{\langle M\rangle\mid M(\langle M\rangle)=reject\}\\ B &= \{\langle M\rangle\mid M(\langle M\rangle)=accept\} \end{align}$$ In other ...
3
votes
1answer
45 views

P/Poly class - undecidable lanauge

I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me. as I learned in class, a turing machine M accepts language L with advice $ {a_n} $ if: M(x,$ a_|x| ...
2
votes
1answer
39 views

Disprove that a function exists that counts the turing machines that halt on $\epsilon$

Let $L(M_k) = \{ \langle M \rangle | M \text{ halts on }\epsilon \} \cap \Sigma^k $ Disprove that $\exists f\colon N \rightarrow \Sigma^* . f(k)=\langle M_k \rangle$. I am not sure where I ...
0
votes
0answers
27 views

Proving that $L=\{ \langle M \rangle \colon L(M)=L(M)^R \}$ is undecidable [duplicate]

I'm trying to show that $L=\{ \langle M \rangle \colon L(M)=L(M)^R\}$ is undecidable, but I don't even know where to begin. Google wasn't much of a help, maybe because it's hard describing the ...
5
votes
0answers
97 views

What are the strongest known type systems for which inference is decidable?

It's well known that Hindley-Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...
1
vote
1answer
54 views

Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $

$A_{TM} = \{<M,w> | $ M is a TM and M accepts w $\}$ $H_{TM} = \{<M,w> | $ M is a TM and M halts on w $\}$ I thought that $L = H_{TM} \cap \overline{A_{TM}} \in R$ But I saw the proof ...
0
votes
0answers
30 views

mapping reduction for every recursive language [duplicate]

how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$ I can do a reduction $A \leq_m B$? [EDIT] My try: $A$ is decidable therefore it has a turing ...
1
vote
1answer
50 views

Can Reduction for Undecidability/Decidability Problems Go Both Ways?

This Problem sparked my question: Does a TM $M$ enter state $q$ on input $w$? I proved it was undecidable in this format using the Halting Problem as a subroutine: ...