Course details

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 in this 12-video course, in which learners can examine how to identify limitations and complexities in computation and how to apply P and NP classes to manage them. Begin by recalling the machine learning analytical capabilities of grammar, then look at context-free grammar normal forms, using Chomsky normal forms and Greibach normal forms to manage context-free grammars. Describe pushdown automata and features of nondeterministic pushdown automata. This leads on to Turing machines, their capabilities, and the prominent variations in the building themes of Turing machines. Learners explore the concept of finite transducers, and the types of finite transducers. Recall the underlying limitations of computations and the limitations of computational theory, and the complexities of computation, computational theory complexities, and how it can impact Turing machine models and language families. Learn about handling computation complexities with P class and handling computation complexities with NP class. The concluding exercise involves describing properties and variations of Turing machines, types of finite transducers, and properties of recursively enumerable languages.



Expected Duration (hours)
0.8

Lesson Objectives

Computational Theory: Using Turing, Transducers, & Complexity Classes

  • Course Overview
  • 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