Introduction to the Theory of ComputationDiscusses such topics as: regular languages; context-free languages; Church-Turing thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability. |
From inside the book
Results 1-3 of 8
Page 158
Michael Sipser. THEOREM 5.4 EQTM is undecidable . PROOF IDEA Show that , if EQTM were decidable , ЕTM also would be decid- able , by giving a reduction from ETM to EQTM . The idea is simple . ETM is the problem of testing whether the ...
Michael Sipser. THEOREM 5.4 EQTM is undecidable . PROOF IDEA Show that , if EQTM were decidable , ЕTM also would be decid- able , by giving a reduction from ETM to EQTM . The idea is simple . ETM is the problem of testing whether the ...
Page 175
... EQTM is neither enumerable nor co - enumerable . PROOF First we show that EQTM is not enumerable . We do so by showing that ATM is reducible to EQTM . The reducing function ƒ works as follows . F = " On input ( M , w ) where M is a TM ...
... EQTM is neither enumerable nor co - enumerable . PROOF First we show that EQTM is not enumerable . We do so by showing that ATM is reducible to EQTM . The reducing function ƒ works as follows . F = " On input ( M , w ) where M is a TM ...
Page 176
... EQTM , as desired . To show that EQTM is not enumerable we give a reduction from ATM to the complement of EQTM , namely , EQTM . Hence we show that ATM m EQTM . The following TM G computes the reducing function g . G = " The input is ...
... EQTM , as desired . To show that EQTM is not enumerable we give a reduction from ATM to the complement of EQTM , namely , EQTM . Hence we show that ATM m EQTM . The following TM G computes the reducing function g . G = " The input is ...
Contents
Formal definition of a nondeterministic finite automaton | 1 |
Proof by construction | 19 |
Regular Languages | 29 |
Copyright | |
8 other sections not shown
Other editions - View all
Common terms and phrases
A₁ accepting computation history alphabet arrows automata binary Boolean C₁ called Chomsky normal form clause configuration construct contains context-free grammar context-free language convert corresponding decidable language decide ATM defined describe deterministic diagram directed graph domino edges empty stack encoding enumerable EQTM equivalent example finite automaton following figure formal definition GNFA graph G halts HAMPATH induction input string integers label length M2 accepts machine accepts mapping reducibility match mathematical N₁ nodes nondeterminism nondeterministic finite nondeterministic finite automaton nondeterministic Turing machine notation NP-complete output pair parse tree polynomial polynomial time algorithm polynomial time reducible PROOF IDEA prove pumping lemma pushdown automaton q₁ recursion theorem regular expression regular languages reject rule running SAN DIEGO satisfying assignment Scan sequence simulate single-tape Stage steps SUBSET-SUM substring tape transition function true Turing machine undecidable variable write