Skip to content

Instantly share code, notes, and snippets.

View alanboy's full-sized avatar

Alan Gonzalez alanboy

View GitHub Profile
@jameshfisher
jameshfisher / halting_problem_javascript.md
Last active September 7, 2017 01:04
A proof that the Halting problem is undecidable, using JavaScript and examples

Having read a few proofs that the halting problem is undecidable, I found that they were quite inaccessible, or that they glossed over important details. To counter this, I've attempted to re-hash the proof using a familiar language, JavaScript, with numerous examples along the way.

This famous proof tells us that there is no general method to determine whether a program will finish running. To illustrate this, we can consider programs as JavaScript function calls, and ask whether it is possible to write a JavaScript function which will tell us