
The course will include topics from
Main topic this semester: Quantum computing, theory and systems;
Stochastic machines, quantum automata (security revisited);
Review of languages, grammars and machines, Chomsky hierarchy, decidability;
The theory of recursive and partial recursive functions;
Models of computation such as Turing machines, Markov algorithms,
Post systems, recursive functions, lambdacalculus;
Markov models, Hidden Markov Models (HMM);
Computability: what problems can be solved? Problem as a 'property'/membership in
a language ('computable' sets), Universal language (Lu), diagonalization language (Ld), 'properties' of r.e. languages, nonr.e. languages, Rice's theorems;
Computational complexity, relations among complexity measures, DTIME, NTIME, DSPACE, NSPACE, hierarchy theorems;
Intractable problems, Polynomial time and space, NPcomplete, PSPACEcomplete, complements of complexity classes;
Topics in formal languages: properties of FSA and regular languages, FSA with output, MyhillNerode theorem, DCFL, normal forms of CFG, ambiguity of CFG, closure properties of (full) trios,
LL(k) grammars, LR(k) grammars;
Selfmodifying machines, cellular automata models (Wolfram), viruses, computer security;
Applications of automata theory in coding, secure communication protocols, cryptography; Alternative (natural) models of computation: neural networks, genetic algorithms, swarm technologies.
Catalog Description
Definition of grammars and languages, recursive and recursively enumerable sets, decidability, and the Chomsky hierarchy of languages and their relation to models of automata.
 