All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
40 views

It is decidable whether a pushdown automaton will accept a word? [duplicate]

I'm asking myself if the problem of decide whether a push down automaton will accept a word is decidable. I would say that you can simulate a push down automaton with a Turing Machine and, if it ...
8
votes
3answers
3k views

Show that there are infinitely more problems than we will ever be able to compute

I was looking at this reading of MIT on computational complexity and on minute 15:00 Erik Demaine embarks on a demonstration to show what is stated in the title of this question. However I cannot ...
1
vote
1answer
107 views

Prove Halting on all Inputs is not in RE simulation

I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
2
votes
1answer
76 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
1answer
80 views

Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

I'm stuck on this problem: Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$...
1
vote
1answer
109 views

Prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is **not** recursively enumerable

So I tried to prove that $D =\{x \in \mathbb{N} | \Phi_x(x)\uparrow\}$ is not recursively enumerable in the following way: let's suppose that $g$ is the computable function that represents $D$ $$g(x) ...
2
votes
1answer
63 views

Proving or disproving a set of total functions is countable

Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. ...
3
votes
1answer
276 views

The Church-Turing-Thesis in proofs

Currently I'm trying to understand a proof of the statement: "A language is semi-decidable if and only if some enumerator enumerates it." that we did in my lecture. One direction of the proof goes ...
3
votes
1answer
326 views

Construction of the complement of universal Turing machine - where is the catch?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct ...
2
votes
1answer
277 views

A confusion about the Reduction via Computation History

[Updates: Thanks for @Raphael 's notification, I delete the screenshot of the book and type the $LaTex$ materials] In Sisper's Intro to the theory of Computation, there is a reduction method via ...
0
votes
0answers
69 views

Does a given Turing machine works in time limited by $5n$?

There doesn't exist an algorithm which decides on the following problem: Does a given Turing machine work in time limited by $5n$? $n$ is the length of $w$. $w$ is an input word. The answer is: No, ...
1
vote
2answers
235 views

A question about an input in a Halting Problem proof

Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen. $H(p,i)$ returns $1$ if program $p$ halts on input $i$. $H(p,i)$ returns $0$ if program $p$ ...
-1
votes
2answers
87 views

Can someone help me understand this proof: there exists a complement of an RE language is not RE

I'm trying to understand this proof in Peter Linz's book The math just doesn't make any sense, I don't understand how this is a proof. First of all, the author says let's define a language such that: ...
-1
votes
2answers
172 views

Is this a valid proof of uncomputability of a function that doesn't use diagonalization?

Let's take the function $f = \{(0,\pi)\}$. If I want to prove that such function is uncomputable I can simply say that calculating $\pi$ from $0$ would necessarily require infinitely many steps,...
2
votes
1answer
33 views

Can an alphabet be extended in a reduction proof? (with sample problem)

So I am working on solving a problem on whether following language is decideable: $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
2
votes
1answer
201 views

How do we know that the reduction is correct?

I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable. Here's my reasoning: Let's say that we want ...
6
votes
2answers
497 views

Proof (by contradiction) of the emptiness problem

I fail to understand the proof of the Emptiness Problem $E_{TM} = \{\langle M \rangle | M $ is a TM and $L(M) = \emptyset\}$ 1) Use the description of $M$ and $w$ to construct $M_1$, which on Input $...
0
votes
1answer
61 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
4
votes
1answer
55 views

How to handle an undefined case with µ-recursive functions?

How to construct my proof and generally what should I aim to get when showing a function is $\mu$-recursive? Should I transform it in some of the basic functions using the given operators? For ...
0
votes
2answers
1k views

Prove the halting problem is undecidable using Rice's theorem

Is it possible to prove that the Halting problem is undecidable using Rice's theorem? Here's what I've tried and failed: We want to reduce Rice's Theorem (decide if a language has the nontrivial ...
1
vote
2answers
192 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 ...
28
votes
2answers
774 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 ...
0
votes
1answer
239 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 be ...
32
votes
5answers
8k views

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
5
votes
1answer
280 views

How rule 110 would be proven to be universal if the tag system did not exist?

I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
2
votes
0answers
161 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
1k 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 ...
2
votes
0answers
21 views

Computational models - proving language is decidable [duplicate]

I tried to prove that the following language is recursive/decidable/in R: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_\text{TM,epsilon}\cap \Sigma^k $$ where $H_\text{TM,epsilon}=\{\langle ...
7
votes
3answers
459 views

Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup

I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$ where $H_{\mathrm{TM},\varepsilon}=\{\...
0
votes
2answers
120 views

Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?

This is text of an exercise I am working on: Given a binary encoding scheme for the set of the deterministic Turing machines with alphabet $\{0,1\}$ and a bijective and computable function $f: \{0,1\...
30
votes
7answers
6k 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 ...
2
votes
0answers
48 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
6
votes
2answers
9k views

How to prove that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable? I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts ...
40
votes
4answers
12k views

What are common techniques for reducing problems to each other?

In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
43
votes
2answers
14k views

How to show that a function is not computable?

I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
5
votes
2answers
406 views

Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem. Halting ...
2
votes
2answers
438 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where $\...
4
votes
1answer
267 views

How to prove or disprove that f is computable?

If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable. I want some hints on how to prove/disprove the ...
5
votes
2answers
591 views

If a predicate is not computable, what can be said about its negation?

Doing the following exercise: Let $\overline{HALT(x,y)}$ be defined as $\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$ Show that it is not computable. Just ...
4
votes
4answers
1k views

What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
7
votes
2answers
3k views

Mapping Reductions to Complement of A$_{TM}$

I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$ where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
10
votes
2answers
727 views

Can we show a language is not computably enumerable by showing there is no verifier for it?

One of the definitions of a computably enumerable (c.e., equivalent to recursively enumerable, equivalent to semidecidable) set is the following: $A \subseteq \Sigma^*$ is c.e. iff there is a ...