State and prove the Halting problem.

2.6kviews

written 5.6 years ago by

teamques10 ★ 65k

• modified 3.5 years ago

ADD COMMENT EDIT

1 Answer

182views

written 5.6 years ago by

teamques10 ★ 65k

Input − A Turing machine and an input string w.

Problem − Does the Turing machine finish computing of the string w in a finite number of steps? The answer must be either yes or no.

Proof − At first, we will assume that such a Turing machine exists to …

Create a free account to keep reading this post.

and 5 others joined a min ago.

ADD COMMENT EDIT

Please log in to add an answer.