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

learn more… | top users | synonyms

1
vote
0answers
21 views

Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable [on hold]

I have a homework assignment in which I am required to determine if $$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$ is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$ Now, my ...
6
votes
4answers
118 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
19
votes
7answers
1k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
-1
votes
1answer
26 views

Use Rice's theorem to prove the following is undecidable

Given the language $L=\{\alpha \mid M_{\alpha}(x)=x^3$ for all $x\in\{0,1\}^*\}$. Prove using Rice's theorem that $L$ is undecidable. Rice's theorem: Let $P$ be a set of all computable functions ...
0
votes
1answer
37 views

Prove Undecidability: TM M enters each of its states on Input W?

Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$? How to prove that the problem is ...
0
votes
1answer
22 views

Decidable Problem

How should I go about showing that the following problem is decidable: Given DFAs M1 and M2, is L(M1) ⊆ L(M2)? What is the general strategy to prove ...
2
votes
1answer
20 views

Undecidable definition of pure function?

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
1answer
46 views

Infinite u decidable languages

I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the ...
3
votes
1answer
24 views

Why is it true that the relation R and its negation are not semi decidable?

An example given for a relation R where its negation and itself are not semi-decidable was: $R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold. ...
7
votes
3answers
166 views

Is Deciding Decidability Decidable?

I am wondering if deciding the decidability of problem is a decidable problem. I am guessing not, but after initial searches I cannot find any literature on this problem.
2
votes
2answers
60 views

Recursive language subtracted from recursively enumerable language

This is a homework problem but I am awfully confused. The problem reads as follows: If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the ...
10
votes
1answer
279 views

Is it decidable whether a pushdown automata recognizes a given regular language?

The problem whether two pushdown automata recognize the same language is undecidable. The problem whether a pushdown automata recognizes the empty language is decidable, hence it is also decidable ...
2
votes
2answers
32 views

Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Suppose I have a set of strings $S$ that is generated from the alphabet. Suppose I have a DFA $D$ and a CFG $G$, are the questions of $\{D\mid D\text{ is a DFA and }L(D) = S\}$ and $\{G\mid G\text{ ...
2
votes
1answer
106 views

Turing recognizable -decidable languages-

I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not ...
0
votes
0answers
11 views

Can we compute the fastest algorithm for a given total function? [duplicate]

First let $f$ be the description of a partial function. Let $\operatorname{optimize}(f)$ be a function that returns a description of the "fastest" Turing machine that computes $f$ for some sensible ...
4
votes
2answers
149 views

Unprovable Post correspondence problem instance

Since there is no algorithm for the post correspondence problem, there exists an instance of this problem such that we can neither prove that the instance is positive nor prove that the instance is ...
-1
votes
1answer
83 views

Many-one-reductions with finite image

Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$. How can $f(K)$ be a finite set? Why if‌ $B$ is recursive, is $f^{-1}(B)$ ...
2
votes
3answers
141 views

Implications of Rice's theorem

Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong. Lets take some non-trivial property of the set of ...
2
votes
1answer
51 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
-1
votes
1answer
50 views

Some Algorithm on Decidablitly [closed]

Anyone could correct me that Why just (1) is False. i'm not sure why others are true: ( G is a Context Free Grammar). any brief description? There is an algorithm that decides whether the ...
-1
votes
1answer
22 views

P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q [closed]

My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q
1
vote
0answers
89 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
3
votes
1answer
67 views

(Un)Decidability of disjoint decidable and undecidable sets

I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable? I am almost sure that it is ...
-1
votes
1answer
80 views

Let A,B be languages. If A is decidable and B undecidable, then A reducible to B

So I'm learning for an upcoming exam and there's a specific problem which I can't show: Let A be decidable and B undecidable, then $A \le B$ Can someone give me a hint how to solve that? ...
4
votes
2answers
139 views

Can a quantum computer (theoretically) do things a classical computer (literally) can't?

I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
0
votes
1answer
40 views

NXOR for 2 inputs on a turing machine, in P?

Question: L is the language of $\langle M,x,y\rangle$ s.t TM $M$ accepts both inputs $x$ and $y$ or doesn't accept either. Prove that given some $M$, finding 2 inputs $x$ and $y$ s.t. $\langle ...
3
votes
1answer
213 views

What is the exact meaning of a Predicate, decidability and computability?

In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as: By a predicate or a Boolean-valued function on a set ...
2
votes
1answer
368 views

Reducing a non-RE language to its complement

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...
1
vote
1answer
67 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
2
votes
1answer
164 views

Using Generalized Rice's Theorem to Prove Decidability

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to ...
1
vote
3answers
119 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
1
vote
1answer
62 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if ...
-1
votes
2answers
57 views

Relation between sets and partially computable functions

I encountered this problem. Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f_1, f_2$ and $f_3$ are partially computable functions that are defined as ...
0
votes
0answers
34 views

Is it decidable whether a TM accepts more than one word?

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can ...
4
votes
1answer
70 views

Is the difference of a non-recursive and recursive set recursive?

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
1
vote
1answer
47 views

Is the extension of every undecidable theory undecidable?

While it is not the case that the extension of every decidable theory is decidable, is it true that: the extension of every undecidable theory undecidable? In other words, given an undecidable ...
-2
votes
3answers
207 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
-1
votes
1answer
40 views

Why apply the assumed decide für HALT to the input and its code?

In the lecture notes I have got in class I have the following proof for the halting problem not being recursive Assume $H$ is recursive and TM $M_1$ decides it. Construct $M_2$ that gets ...
0
votes
2answers
75 views

Is emptiness of the intersection of the languages of two TMs decidable? [duplicate]

Let $\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$. How do I know if this language is decidable or not? And How do I prove ...
1
vote
1answer
30 views

Model Checking: hardware vs software

In short: What is the basic difference that allows model checking for hardware to be "easily" solvable, but makes it undecidable for software? I guess it has to boil down to the difference between ...
1
vote
2answers
206 views

Undecidability in the context of modern programming languages

Imagine a program, executed by an interpreter to be a Turing Machine. Consider this code: x = read_input print x Does undecidability mean that there may possibly ...
2
votes
1answer
33 views

Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

Is this problem decidable? Given two representations of Turing machines $R(M_1), R(M_2)$, is the length of the computation of $M_1$ longer than the length of the computation of $M_2$ on every input? ...
-1
votes
1answer
84 views

Proof that L(M) = {accepts the string 1100 } is undecidable

Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$ To proof that the language $L$ is undecidable I should reduce something to $L$, right? I tried ...
0
votes
0answers
21 views

How to show {n:U(n,x) is defined for all x} is not enumerable

U(n,x) is Gödel universal function, and we need to show {n:U(n,x) is defined for all x} is not enumerable. I do not have any clue right now. Anyone can give me some hint about this question.
1
vote
1answer
64 views

Satisfiability of first-order logic is undecidable?

I struggle with understanding why the satisfiability in the first-order logic is undecidable. Could you explain it with some examples? I've also seen that satisfiability in some first-order formulas ...
4
votes
1answer
99 views

Decide whether there exists a walk of weight exactly k

Consider the following problem: Input: a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v_1, v_2 \in V$, and a weight $k \in \mathbb{Z}$ Question: ...
2
votes
2answers
283 views

Is this variant of ATM decidable?

Ok so I understand how $\mathrm{ATM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$}\}$ is undecidable. Is this because $w$ is a variable? What if the parameter is fixed? ...
0
votes
1answer
49 views

Rice's Theorem: implication of having an undecidable property

I understand the assumptions that have to be true about a property or set of properties in a Turing machine description for Rice's Theorem to apply. But then what? If a set of Turing machines have ...
0
votes
2answers
517 views

Decidability of empty intersection of two languages accepted by Turing machines

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not. I have a language $\qquad\displaystyle L = \{ (R(M_1), R(M_2)) ...
3
votes
2answers
127 views

Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in ...