ECE 595E Lecture 3: Computability

By Peter Bermel

Electrical and Computer Engineering, Purdue University, West Lafayette, IN

View Presentation

Additional materials available (4)

Category

Online Presentations

Published on

Abstract

Outline:

  • Overview • Definitions
  • Computing Machines
  • Church-Turing Thesis
  • Polynomial Time
  • Example

Cite this work

Researchers should cite this work as follows:

  • Peter Bermel (2013), "ECE 595E Lecture 3: Computability," https://nanohub.org/resources/16567.

    BibTex | EndNote

Time

Location

EE 226, Purdue University, West Lafayette, IN

Tags

  1. course lecture
  2. Programming
  3. Simulation
ECE 595E Lecture 3: Computability
  • Lecture 3: Computability 1. Lecture 3: Computability 0
    00:00/00:00
  • Outline 2. Outline 15.448782115448783
    00:00/00:00
  • Overview from First Lecture 3. Overview from First Lecture 39.806473139806478
    00:00/00:00
  • Definitions 4. Definitions 77.510844177510847
    00:00/00:00
  • Turing Machine 5. Turing Machine 221.42142142142143
    00:00/00:00
  • Turing Machine: Behavior in Each State 6. Turing Machine: Behavior in Ea… 416.54988321654992
    00:00/00:00
  • Time Constructible Functions 7. Time Constructible Functions 581.41474808141481
    00:00/00:00
  • Turing Machine: Key Properties 8. Turing Machine: Key Properties 748.08141474808144
    00:00/00:00
  • Universal Turing Machines 9. Universal Turing Machines 926.45979312645977
    00:00/00:00
  • Other Computing Machines 10. Other Computing Machines 1013.9139139139139
    00:00/00:00
  • Church-Turing Thesis 11. Church-Turing Thesis 1370.7374040707375
    00:00/00:00
  • Uncomputability 12. Uncomputability 1959.1257924591259
    00:00/00:00
  • Big-Oh Notation 13. Big-Oh Notation 2605.5388722055391
    00:00/00:00
  • Polynomial Complexity 14. Polynomial Complexity 2804.0040040040039
    00:00/00:00
  • Other Classes 15. Other Classes 3025.4587921254588
    00:00/00:00
  • Examples 16. Examples 3042.0754087420755
    00:00/00:00
  • Next Class 17. Next Class 3052.4190857524191
    00:00/00:00
Pop Out