0. Introduction & Halting Problem

PDFContent 30/01/23

Automata - Ways of

	Formative Language	Automita	Reg Ex / Grammar
Type 3	Regular Languages	Finite Automata (Deterministic or Non-Deterministic)	Regular Expression
Type 2	Context-free Languages	Push down automita	Context-free grammar
Type 1	Context Sensitive Languages	Turing Machine	Grammar
Type 0	Recursively Enumerable Languages	Turing Machine	Grammar

Halting Problem

void weird (char *code){
if holts(code, code)
    while(n);
else
    return;
}

Cannot prove that any program will stop

• Will Spooner

It is impossible to write a program that decides if another, arbitrary, program terminates (halts) or not