CSc 422 - Computability


1. Knowledge of characterization of computability functions, decision problems and their relationship to model of computations.
2. Knowledge of famous issues in computability. Hilbert's 10th problem & its aftermath, Church's thesis, post Markov theorem & application.
3. Knowledge of extended models of computation—Oracle methods.
4. Knowledge of computational randomness: Kolmogorov, Chaitin.
5. Knowledge of the rapid shift in ideas about computing, e.g. DNA computing, quantum computing, neural computing.