awarded
comment
Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
so x is just a string of like say all ones, and is used only to count how many steps we have done?
comment
Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
As I understand it, checking whether M' is empty only decides the problem of whether M halts on input x in |x| or less steps. This is different from the halting problem in general; for example, |x| is finite and of course determining if a machine halts in a finite number of steps is decidable. So what am i misunderstanding?
comment
Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
I don't think that you are explaining the proof or answering my questions, but rather just restating what is written above.
comment
Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"
Asking whether a TM halts in a finite number of steps (|x| in the proof above) is decidable. So how would the problem of detecting equality outlined above provide a way of solving the halting problem?
revised
Loading…
Loading…
comment
Is the halting problem decidable for TMs that do not write to the tape?
Is this not correct because the situation where it keeps moving to the blanks on the right? And each movement to the right is a new configuration. Does this mean I have to prove that the TM does not move to the right forever? I’m trying to understand the link you gave me but I’m not quite there with it.
comment
Is the halting problem decidable for TMs that do not write to the tape?
Okay thank you very much. “ you haven't proven that if the TM doesn't repeat a configuration, it will halt.” Can’t I just say that if a TM doesn’t repeat a configuration then because there are a finite number of configurations, the TM must finish in finite steps, in other words halt?
comment
Is the halting problem decidable for TMs that do not write to the tape?
I didn’t get to finish reading that answer that was posted. I thought it looked helpful. Can you repost as a comment?
comment
Is the halting problem decidable for TMs that do not write to the tape?
My question was closed ?
comment
Understanding lemma found in proof of quotient construction for DFAs
@D.W. please stop editing my post. In my view, the edits you want to make reduce the quality of my post.
revised
Understanding lemma found in proof of quotient construction for DFAs
rolled back to a previous revision
Loading…
revised
Understanding lemma found in proof of quotient construction for DFAs
rolled back to a previous revision
Loading…
awarded
revised
Loading…
revised
Understanding lemma found in proof of quotient construction for DFAs
rolled back to a previous revision
Loading…