If you delve deeper into computer science or engineering, you will come across Turing machines. What is the Turing machine? Why do things that don't seem like computers keep coming out? If you major in computer science, especially in the theoretical field, they say you have to learn about Turing machines. Why on earth is that?
00:10 Motivation
02:17 Introduction
03:59 Turing Machine - Definition
06:11 Turing Machine - Automaton notation
07:09 Universal Turing Machine
08:38 Halting Problem - Definable but not computable
10:53 Historical Background
13:16 Church-Turing Thesis
14:43 Turing completness & Turing Equivalence
16:50 Pitfalls of Negative Theories
19:18 Turing Machines & Modern Computers
23:06 Summary
25:17 My humble opinion
References
- P.Benioff, "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines," *J. of Stat. Phys.* 22, 563–591 (1980), https://doi.org/10.1007/BF01011339
- A.Church, "An Unsolvable Problem of Elementary Number Theory," *American J. of Math.* 58(2), 345-363 (1936), https://doi.org/10.2307/2371045
- J.E.Hopcroft, J.D.Ullman, 1979, *Introduction to Automata Theory, Languages, and Computation,* Addison-Wesley Publishing Co. Inc., USA.
- J.E.Hopcroft, R.Motwani, J.D. Ullman, 2006, *Introduction to Automata Theory, Languages, and Computation (3rd Ed.),* Addison-Wesley Longman Publishing Co. Inc., USA.
- E.L.Post, "Finite Combinatory Processes-Formulation 1," *J. of Symbolic Logic* 1(3), 103-105 (1936), https://doi.org/10.2307/2269031
- H.T. Siegelmann, E.D. Sontag, "On the Computational Power of Neural Nets, " *J. of Comp.and Sys. Sci.* 50(1), 132-150 (1995), https://doi.org/10.1006/jcss.1995.1013
- A.M.Turing, "On computable numbers, with an application to the Entscheidungsproblem," *Proc. of London Math. Society* 58, 230–265. (1936), https://doi.org/10.1112/plms/s2-42.1.230