તેમના અતિમહત્ત્વના પેપર "ઓન કમ્યૂટેબલ નંબરસ્, વીથ એન એપ્લીકેશન ટુ ધી એન્ટ્સેઈડંગસપ્રોબ્લેમ (Entscheidungsproblem) ",[૧૭] ટ્યુરિંગે ગણતરી અને પ્રૂફની મર્યાદાઓ પરના 1931ના કુર્ટ ગોડેલનાં પરિણામો પર પુનઃસૂત્રો તારવી, ગોડેલના વૈશ્વિક ગાણિતિક આધારિત યાંત્રિક ભાષા સાથે ફેરબદલી કરીને યાંત્રિક અને સરળ ડિવાઈસો મૂક્યા, જે ટ્યુરિંગ મશીનો તરીકે જાણીતાં બન્યાં. તેમણે સાબિત કર્યું કે કેટલાંક આવા મશીનો કોઈપણ કલ્પના જો અલ્ગોરિધમ પ્રમાણે રજૂ કરવામાં આવે તો તેની ગાણિતિક ગણતરી કરવા માટે તે સક્ષમ બનશે. તેઓ સાબિત કરતાં ગયા કે ટ્યુરિંગના મશીન માટે અચકાવવાની સમસ્યા અનિશ્ચિત છે જે સૌ પ્રથમ વખતે દર્શાવતાં એન્ટ્સેઈડંગસપ્રોબ્લેમ (Entscheidungsproblem) નો કોઈ ઉકેલ નથી કે એવું સાબિત કરતા ગયા હતા. તે નક્કી કરવું શક્ય નથી, વાસ્તવમાં, જ્યારે પણ ગાણિકીત ક્રિયા ટ્યુરિંગ મશીનને આપવામાં આવશે ત્યારે તે હંમેશા અચકાશે કે કેમ. જો કે તેમના લેમ્બડા કલનને આદર આપવામાં એલોન્ઝો ચર્ચને સમકક્ષ પ્રુફ પથી તેમનું પ્રુફ પ્રકાશિત થયું હતું, તે વખતે ટ્યુરિંગ ચર્ચના કામથી અજાણ હતા.