[FrontPage] [TitleIndex] [WordIndex

Wrap-up of automata theory:

Finite State Machines (deterministic and non-deterministic)

Accept DFA (Deterministic Finite Automata) = Given a DFAF + astring W, does F accept W? AcceptNFA can reduce to the DFA. EmptyDFA Does DFA F accept any strings (can do by flooding)

Equivelent- Do DFAs F&G accept some language? Push Down Automata

Turing Machines:

Linear Bounded Automata: Ontecs Sensitive, Grammars, |Lft Side| < |Right Side< With CFGs the terminals are set by the rules and don¡¦t dissappear. With Grammars, the terminals are only determined by the input string and can be changed

Decidision: Prolems: computaoi

Accpet PDA: is decidable Empty PDA is decidable

Every FSM is recognizable by Push-Down Automata

Turing machingi= and pk I can write a TM that takes as an input, that takes as an input M-descrippiol, W- input to that T, M It what M would do on W?

Z+ |1, 2, ...(\n) Z |0, 1, -1, 2, -2,¡K (\n) Q or Z2 |¡K (\n)

Each list means the same thing as they can be mapped to each other

R proof by contradiction:

(Diagonalism) If nth digit of nth # is 3, nth digit of w is 7. Otherwise, nth digit of w is 3

There are a countable number of Turing machines: (there exists) countably many TMs. 1. 0 2. 1 3. 00 4. 01 5. 10 6. 11 2n strings of n (if continued); these are an ordered list of finite strings of arbitrary length. Check syntax and cross out the ones that aren¡¦t TMs.

For a language, say 0*1*, you can create a bit string stating whether the binary list from above is following that language. (111101) „³This means that if I could count languages, I could define a language not on the list. But I can¡¦t.


Why isn¡¦t running Univ. Machine the answer?

Proof by contradiction: Assume Halt exists. Build Halt¡¦(M)=Halt(M, M) Now build P(M)={run Halt¡¦ on M=Halt(M, M)

P(P)?=(not)Halt¡¦(P1)= not( Halt(P,P))

Church Turing: Any model of effective computation will resort to a Turing Machine.

2013-07-17 10:43