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

learn more… | top users | synonyms

0
votes
1answer
91 views

Prove whether this problem is decidable or undecidable

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
49 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
48 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
45 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
55 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
143 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
273 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
787 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
123 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
36 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
40 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
68 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
62 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
34 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
131 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 ...
3
votes
1answer
90 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
87 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
81 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
76 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
328 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
54 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
22 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
44 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
27 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
67 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
42 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
31 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
58 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
221 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.
23
votes
2answers
390 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
61 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
123 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
68 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
60 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
365 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
46 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
105 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 ...
9
votes
2answers
85 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
230 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
73 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
51 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
114 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
72 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
153 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. ...
1
vote
1answer
85 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 ...