ToC Flashcards
Turing Enumerator
Slide 14, lecture 1
Acceptance Problem Explanation
Slide 19, lecture 1
A_TM is undecidable/Diagonalization met bewijs
Slide 24, lecture 1
complement(A_TM) is T-unrecognizable
Slide 25, lecture 1
Reducibility method => concept
Slide 3, lecture 2
Reducibility Method on Halt_TM
Slide 2, lecture 2
E_TM is undecidable
Slide 4, lecture 2
Mapping Reducibility concept + proof
Slide 5, lecture 2
Mapping reduction - properties
Slide 6, lecture 2
E_TM is T_unrecognizable
Slide 9, lecture 2
EQ_TM and complement(EQ_TM) are T_unrecognizable
Slide 10, lecture 2
The Recursion Theorem
Slide 15, lecture 2
A_TM is undecidable - new proof
Slide 16, lecture 2
Time Complexity classesdefinition TIME (runs in time?)
Slide 7, lecture 3
Multi-tape vs 1-tape time
Slide 8, lecture 3
The Class P
Slide 10, lecture 3
Path element of P
Slide 10, lecture 3