Decidability

9 outubro 2015, 11:00 • José Félix Costa

Halting problem. Decidability.

Pointers:

Goodstein Theorem

Conjectura de Collatz

Turing machines

7 outubro 2015, 10:00 • José Félix Costa

Turing machines: 1-tape, k-tapes, deterministic and non-deterministic. Concepts related with a Turing machine.

Pointers:

Centenário do Nascimento de Alan Turing

Máquina de Turing em LEGO

Context-free languages

2 outubro 2015, 11:00 • José Félix Costa

Pumping lemma for context-free languages.

Pushdown automata

30 setembro 2015, 10:00 • José Félix Costa

Pushdown automata.

Grammar theory

25 setembro 2015, 11:00 • José Félix Costa

Grammars, context-sensitive grammars, context-free grammars, regular grammars.

Gerative trees.

Chomsky hierarchy.

NOTE: You may be interested in seeing Filosofia da Linguagem, Wittgenstein in Cambridge, Noam Chomsky on mistérios da linguagem. Noam Chomsky "Grammar, Mind and Body - A Personal View". Noam Chomsky - Current Problems in the Study of Language and Mind.