Masalah Halting adalah masalah dalam ilmu komputer. Masalahnya adalah melihat sebuah program komputer dan mencari tahu apakah program tersebut akan berjalan selamanya atau tidak. Kita mengatakan bahwa sebuah program "memecahkan masalah halting" jika program tersebut dapat melihat program lain dan mengetahui apakah program lain itu akan berjalan selamanya atau tidak.

Contohnya, program seperti ini:

 sementara Benar: lanjutkan;

akan berputar selamanya, tetapi program

 sementara False: lanjutkan; 

berhenti dengan sangat cepat.

Apakah ada program yang memecahkan masalah halting? Ternyata tidak ada. Kita buktikan fakta ini dengan menunjukkan bahwa jika ada program yang memecahkan masalah halting maka sesuatu yang mustahil terjadi. Jadi, untuk saat ini kita akan bertindak seolah-olah benar-benar ada program yang memecahkan masalah halting. Di sini, P adalah sebuah fungsi yang akan mengevaluasi fungsi F (dipanggil dengan argumen I) dan mengembalikan nilai benar jika berjalan selamanya dan salah jika tidak.

 def P(F, I): if F(I) berjalan selamanya: return True; else: return False;

P dapat melihat program apapun dan mencari tahu apakah program itu akan berjalan selamanya atau tidak. Kita menggunakan P untuk membuat program baru yang akan kita sebut Q. Apa yang dilakukan Q adalah melihat program lain dan kemudian menjawab pertanyaan berikut: "Jika kita menjalankan program ini dan membuatnya melihat salinan dari program itu sendiri, apakah program itu akan berjalan selamanya?". Kita bisa membuat Q karena kita memiliki P. Yang perlu kita lakukan adalah memerintahkan Q untuk membuat program baru yang merupakan program lama yang melihat dirinya sendiri, dan kemudian menggunakan P untuk mengetahui apakah program baru itu berjalan selamanya atau tidak.

 def Q(F): mengembalikan P(F, F);

Sekarang kita membuat program lain R. R melihat program lain dan menanyakan jawaban Q tentang program itu. Jika Q menjawab "ya, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, program ini akan berjalan selamanya", maka R berhenti. Jika Q menjawab "tidak, jika kita menjalankan program ini dan membuatnya melihat salinan dari dirinya sendiri, maka program ini tidak akan berjalan selamanya", maka R memasuki perulangan tak hingga dan berjalan selamanya.

 def R(F): if Q(F): return; //terminate else: while True: continue; //loop forever

Sekarang kita lihat apa yang terjadi jika kita membuat R melihat salinan dari dirinya sendiri. Dua hal yang bisa terjadi: ia akan berhenti atau berjalan selamanya.

Jika menjalankan R dan membuatnya melihat salinan dirinya sendiri tidak berjalan selamanya, maka Q menjawab "ya, jika kita menjalankan program ini dan membuatnya melihat salinan dirinya sendiri maka akan berjalan selamanya". Tetapi Q mengatakan ini ketika melihat R itu sendiri. Jadi apa yang sebenarnya Q katakan adalah: "ya, jika kita menjalankan R dan membuatnya melihat salinan dari dirinya sendiri maka akan berjalan selamanya". Jadi: Jika R yang berjalan pada salinan dirinya sendiri tidak berjalan selamanya, maka R akan berjalan selamanya. Ini mustahil.

Jika menjalankan R dan membuatnya melihat salinan dirinya sendiri berjalan selamanya, maka Q menjawab "tidak, jika kita menjalankan program ini dan membuatnya melihat salinan dirinya sendiri, program ini tidak akan berjalan selamanya". Tetapi Q mengatakan ini ketika melihat R itu sendiri. Jadi apa yang sebenarnya Q katakan adalah: "tidak, jika kita menjalankan R dan membuatnya melihat salinan dari dirinya sendiri maka tidak akan berjalan selamanya". Jadi: Jika R yang berjalan pada salinan dirinya sendiri berjalan selamanya, maka R tidak berjalan selamanya. Ini juga mustahil.

Tidak peduli apa yang terjadi, kita mendapatkan situasi yang mustahil. Kita melakukan sesuatu yang salah, dan kita perlu mencari tahu apa itu. Sebagian besar hal yang kita lakukan tidak salah. Kita tidak bisa mengatakan "membuat program melihat salinan dirinya sendiri adalah salah", atau "melihat apa yang dikatakan program lain dan kemudian masuk ke dalam loop jika program itu mengatakan satu hal, dan berhenti jika program itu mengatakan hal lain" adalah salah. Tidak masuk akal untuk mengatakan bahwa kita tidak diperbolehkan melakukan hal-hal tersebut. Satu-satunya hal yang kita lakukan yang kelihatannya salah adalah bahwa kita berpura-pura bahwa program seperti P itu ada sejak awal. Dan karena ini adalah satu-satunya hal yang bisa salah, dan sesuatu pasti salah, maka inilah dia. Inilah bukti bahwa program seperti P tidak ada. Tidak ada program yang memecahkan masalah halting.

Bukti ini ditemukan oleh Alan Turing pada tahun 1936.