EECS 376 Lecture Notes - Lecture 9: Computable Function, Memory Stick, Michael Sipser

• School: U of M
• Department: Electrical Engineering And Computer Science
• Course: EECS 376
• Professor: Martin Strauss

Document Summary

A program m accepts the string w if, on input w, it prints accept and halts. M rejects the string w if, on input w, it prints reject and halts. M accepts is called the language of m , or the language recognized by m , and is denoted. A language is recognizable if some program recognizes it. A program can fail to accept an input by rejecting it, or by looping. If a program halts on all inputs, then it is said to decide its language l(m ). A language is decidable if some program decides it. Lacc = {(hm i, x) : m is a program and m accepts x}. In lecture, we showed that although lacc is undecidable, it is recognizable. U = on input (hm i, w), where m is a program and w is a string: simulate m on input w, if m ever accepts, accept; if m ever rejects, reject .