Church-Turing Thesis
Definition. The Church-Turing thesis asserts that the intuitive notion of an algorithm, a procedure that could in principle be carried out mechanically, is captured exactly by the Turing machine.
It is a thesis and not a theorem because one side is informal: there is no formal definition of "algorithm" to prove anything about. Its support is that every independently proposed formalization, including Church's lambda calculus and general recursive functions, defines the same class of functions, and that no counterexample has been described. The thesis is what upgrades "no Turing machine decides this language" into "no algorithm decides this problem", which is how the undecidability results of Lecture 7 and Lecture 8 are read. It concerns what can be computed at all, never how fast, so a faster device refutes nothing. Discussed in Lecture 6.