What is Computability?

Joel David Hamkins, Professor of Logic, Oxford University
This lecture is based on chapter 6 of my book, Lectures on the Philosophy of Mathematics, published with MIT Press,
mitpress.mit.e....
Lecture 6. Computability
What is computability? Kurt Gödel defined a robust class of computable functions, the primitive recursive functions, and yet he gave reasons to despair of a fully satisfactory answer. Nevertheless, Alan Turing’s machine concept of computability, growing out of a careful philosophical analysis of the nature of human computability, proved robust and laid a foundation for the contemporary computer era; the widely accepted Church-Turing thesis asserts that Turing had the right notion. The distinction between computable decidability and computable enumerability, highlighted by the undecidability of the halting problem, shows that not all mathematical problems can be solved by machine, and a vast hierarchy looms in the Turing degrees, an infinitary information theory. Complexity theory refocuses the subject on the realm of feasible computation, with the still-unsolved P versus NP problem standing in the background of nearly every serious issue in theoretical computer science.

[@WmTyndale]

Wonderfully illuminating presentation even for this nonspecialist mathematician!

[@TheatreCritic]

JDH takes a difficult subject and conveys it with great clarity, covering a lot of ground in a short space of time. I had a similar experience reading Oystein Linnebo. So, perhaps, close familiarity with topics in logic makes for a clear presenter. I imagine Aristotle would have thought so.

[@joeldavidhamkins5484]

Regarding the question about the independence of P vs. NP at the end, let me say a bit more. There is some excellent information and links to other work available here: cstheory.stackexchange.com/q/10044/1061. It seems to me that the logical complexity of P vs. NP is Sigma_2, since it is equivalent to asserting that there is a polynomial-time algorithm for solving SAT. This can be expressed by a statement of the form: exists program p and polynomial f, such that all inputs give right answer in time, and so it has complexity Sigma_2. Statements with such a complexity are not generally amenable to the kind of analysis that Pi_1 statements admit, namely, that if they are independent, then they are true in the standard model.

[@erincarmody8562]

My favorite part was when you said that P vs. NP was like the difference between appreciating a symphony and composing one... really inspiring.

[@erincarmody8562]

I already have the first 20 notes, they have been composing over the years, the joyfulness, The first 10 notes are repeated, to get 20 and they are the same last 20 notes at the end. The end and the beginning are already composed. And then the choir sings. It will be really good in about 19 years.

[@joeldavidhamkins5484]

*Errata:* AT 46:47, I had wanted to say: if p halts on p, then I don't, and if p doesn't halt on p, then I do.

[@thomasbs7338]

At 1:02:49, you say that in place merge sort is O(nloglogn), which I think is false. Comparison based sorting algorithms need Omega(nlogn) comparisons: there are n! permutations of the list and with k comparisons, we can distinguish between 2^k lists, so we need 2^k >= n!, which implies that k is Omega(nlogn). Wikipedia en.wikipedia.org/wiki/Sorting_algorithm?wprov=sfti1 has a table where in place merge sort is given a worst case complexity of nlog^2 n, but they are using log^2 n to mean (log n)^2 for some reason.

[@joeldavidhamkins5484]

Ah, thank you for this correction! I may have misunderstood this notation where I had read it.

[@elcapitan6126]

do you explore any type theory w.r.t. foundations of mathematics (hott as they call it)?

[@ChanelCoco555]

Hi Professor Hamkins, Regarding the halting problem - it seems to me that the usual argument of specifying a program designed to lead to a contradiction by taking itself as input doesn't preclude the possibility of an "almost" general decision algorithm that can decide the halt-ability of almost all programs, as long as the programs avoid certain "pitfalls", such as those in the argument given to disprove the existence of completely general decision algorithm. To what extent can we have insight into the scope of such an "almost" general decision algorithm, and the types of "pitfalls" that the programs that it can decide the halt-ability of need to avoid? Thank you!

[@joeldavidhamkins5484]

Yes, in fact this is precisely the topic of my paper with Miasnikov, where we show that there is a computable algorithm that solves almost every instance of the halting problem, with asymptotic probably one. See projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-47/issue-4/The-Halting-Problem-Is-Decidable-on-a-Set-of-Asymptotic/10.1305/ndjfl/1168352664.full, arxiv.org/abs/math/0504351

[@fredyfredo2724]

Say an amount of t is a space used by the calcul for expressing the result. What is the best order for itself ? The one who do not can prove itself. It's the result and it do not exist. So doesn't exoress yourself is also an order or t is not a unit.

[@alvaromartinezlopez4603]

Thanks for sharing your knowledge. I have quite surprising and annoying the Church-Turing thesis: anything is effectively computable if and only if it can be computed with a Turing Machine”. I cannot understand how such an statement is not proven formally. To me it seems a conjecture. How can we be certain that no one will ever invent a device that can compute more functions than a TM?

[@EWischan]

Thanks for this. The volume is hard to hear fyi.

[@joeldavidhamkins5484]

I'm sorry about this. It sounds fine on my system, so I'm not sure what the trouble could be. I need to find a sound/video engineer!

[@gonzalopolavieja]

@@joeldavidhamkins5484 ​ I hear it very low in Chrome and much better in Mozilla and other browsers.

[@joeldavidhamkins5484]

@@gonzalopolavieja I'll try to correct this issue from next time. For this time, I'm sorry but there is little I know how to do.

[@PhilosophicalTrials]

It sounds ok for me on both my internet browser (Chrome) and in the KZbin app on my tablet.

[@EWischan]

​@@joeldavidhamkins5484 No worries! It's rectified with headphones. The excellent content makes it worth it. ;)

[@davidwilkie9551]

The Algorithm for Truth? Holography Actuality is the Uncertainty Principle Observation of WYSIWYG QM-TIME resonance, superimposed log-antilog nodal-vibrational emitter-receiver density-intensity quantization, floating in No-thing relative-timing, so WYSIWYG is self-defining AM-FM Logarithmic condensation modulation superposition-quantization and picture-plane containment states represent the layering of solid-liquid-gas-plasma phase-locked coherence-cohesion objective-aspects of probabilistic sync-duration correlations/Computation. In My Opinion that is, because it's hyperfluid vertices in vortices manifestation of nodal-vibrational numberness-> Disproof Methodology Philosophy, by default.., here-now-forever re-evolution in/of Eternity-now Perspective.