Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged halting-problem
0
votes
0
answers
1
Ullman (TOC) Edition 3 Exercise 9.2 Question 1 (Page No. 390)
Show that the halting problem, the set of $(M,w)$ pairs such that $M$ halts (with or without accepting) when given input $w$ is $RE$ but not recursive.$ ($See the box on "The Halting Problem" in Section $9.2.4)$
Show that the halting problem, the set of $(M,w)$ pairs such that $M$ halts (with or without accepting) when given input $w$ is $RE$ but not recursive.$ ($See the box on ...
admin
203
views
admin
asked
Jul 21, 2019
Theory of Computation
ullman
theory-of-computation
halting-problem
+
–
0
votes
0
answers
2
Shai Simonson Lectures on TOC
In the "Halting Problem" lecture, the prof. introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove that the halting problem is undecidable. There he asked to change the algorithm ... . It would be great if somebody can shed some light on it. Thanks! https://www.youtube.com/watch?v=e9zzY7uqT8g
In the "Halting Problem" lecture, the prof. introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove tha...
GautamDas
682
views
GautamDas
asked
Apr 9, 2017
Theory of Computation
halting-problem
turing-machine
theory-of-computation
shai-simonson
decidability
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register