Computer Science 3331A/B Chapter Notes - Chapter 19: Halting Problem, If And Only If, Msh2
30 views3 pages
22 Jan 2020
School
Department
Course
Professor
Document Summary
Exist well defined mathematical or not, problems in which no tm exists. Tm m with input alph decides a language l subset * iff for any string w in * If w in l, then m accepts w. If w not in l then m rejects w. Decidable if exists a tm m that decides it. If w in l then m accepts w. If w not in l then m does not accept- can fail to halt or reject. L1 {: tm m halts on some input string w} L2 {: there exists no string on which tm m halts} L3 {: ma and mb are tm that halt on the same strings} In order for string s to be in l1, it must be. Must encode a machine m and string w such that m halts if started on w. Will try to determine deciding/semidecide of languages like l1 l2 l3.
Get access
Grade+
$40 USD/m
Billed monthly
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers