Previous Page

Computational Theory: Using Turing, Transducers, & Complexity Classes

Computational Theory: Using Turing, Transducers, & Complexity Classes


Overview/Description
Expected Duration
Lesson Objectives
Course Number
Expertise Level



Overview/Description

Discover the concepts of pushdown automata, Turing machines, and finite transducers. Examine how to identify the limitations and complexities in computation and also how to apply P and NP classes to manage them.



Expected Duration (hours)
0.8

Lesson Objectives

Computational Theory: Using Turing, Transducers, & Complexity Classes

  • recall the analytical capabilities of grammar
  • use Chomsky normal forms and Greibach normal forms to manage context-free grammars
  • describe pushdown automata and the features of non-deterministic pushdown automata
  • describe Turing machines and their capabilities
  • list the prominent variations of themes that can be used to build Turing machines
  • describe finite transducers and list the prominent types
  • recall the underlying limitations of algorithmic computations
  • recognize how computational complexities can impact Turing machine models and language families
  • recall how to manage computational complexities using P and NP classes
  • define recursive and recursively enumerable languages and their essential properties
  • describe properties and variations of Turing machines, types of finite transducers, and properties of recursively enumerable language
  • Course Number:
    it_mlfdctdj_02_enus

    Expertise Level
    Intermediate