1936'da henüz yirmi dört yaşında olan İngiliz matematikçi Alan Turing, matematiğin temel sorularından birini yanıtlamaya çalışırken, sonradan bilgisayar biliminin temellerinden biri hâline gelecek bir fikir ortaya attı. Turing'in uğraştığı soru, Alman matematikçi David Hilbert'in ortaya koyduğu bir problemle ilgiliydi: Herhangi bir matematiksel önermenin doğru olup olmadığına, sınırlı sayıda adımda kesin bir yanıt verebilecek mekanik bir yöntem var mıdır?

Bu soruyu yanıtlayabilmek için Turing'in önce "mekanik bir yöntem"in ne olduğunu kesin olarak tanımlaması gerekiyordu. Bunun için hayalî bir makine tasarladı. Bu makine, karelere bölünmüş, sonsuz uzunlukta bir kâğıt şeritten ve bu şerit üzerinde hareket eden bir okuma-yazma kafasından oluşuyordu. Kafa, her adımda bulunduğu karedeki sembolü okuyabiliyor, onu silip yerine başka bir sembol yazabiliyor ve şerit üzerinde bir kare sağa ya da sola hareket edebiliyordu. Makinenin ne yapacağı, o anki durumuna ve okuduğu sembole göre önceden belirlenmiş basit bir kurallar tablosuyla belirleniyordu.

Bu makine, ilk bakışta son derece basit, hatta ilkel görünür. Ancak Turing, bu basit makinenin, bir insanın kâğıt ve kalemle adım adım yapabileceği her türlü hesaplamayı yapabileceğini savundu. Daha da önemlisi, Turing "evrensel makine" adını verdiği özel bir makine tasarladı. Bu evrensel makine, başka herhangi bir makinenin kurallar tablosunu şeridinden okuyarak o makineyi taklit edebiliyordu. Yani tek bir makine, kendisine verilen talimatlara göre her türlü hesaplamayı yapabilirdi.

Bu fikir, bugünkü bilgisayarların temel ilkesini önceden haber veriyordu. Bilgisayarlarımız, yeni bir iş için her seferinde yeni bir makine yapmak yerine, farklı programlar yükleyerek farklı işler yapar. Aynı bilgisayar, bir an kelime işlemci, bir an hesap makinesi, bir an da müzik çalar olabilir. Bu esneklik, Turing'in evrensel makine fikrinin somut bir gerçekleşmesidir.

Turing, hayalî makinesini kullanarak Hilbert'in sorusuna olumsuz bir yanıt verdi. Bazı soruların, hiçbir mekanik yöntemle çözülemeyeceğini gösterdi. Bunun en ünlü örneği, sonradan "durma problemi" olarak anılan sorudur. Turing, herhangi bir programın verilen bir girdiyle çalıştırıldığında bir gün durup durmayacağını ya da sonsuza kadar çalışmaya devam edip etmeyeceğini her durumda doğru biçimde belirleyebilecek genel bir yöntemin bulunamayacağını kanıtladı. Bu sonuç, hesaplamanın da sınırları olduğunu, yani bazı sorunların en güçlü bilgisayarlar için bile ilke olarak çözülemez olduğunu gösteriyordu.

Aynı dönemde Amerikalı matematikçi Alonzo Church da farklı bir yöntemle benzer sonuçlara ulaşmıştı. Bu iki yaklaşımın aslında eşdeğer olduğu kısa sürede anlaşıldı. Bugün "Church-Turing tezi" olarak bilinen görüşe göre, mekanik olarak hesaplanabilen her şey, bir Turing makinesiyle hesaplanabilir.

Turing makinesi, hiçbir zaman fiziksel olarak inşa edilmek üzere tasarlanmamıştı. O, bir düşünce aracıydı. Ancak bu soyut fikir, sonraki on yıllarda dünyayı değiştirecek teknolojinin kuramsal temelini oluşturdu.