Dazu bewies er, dass das Halteproblem für Turingmaschinen nicht lösbar ist, d. h., dass es nicht möglich ist, algorithmisch zu entscheiden, ob eine Turingmaschine, angesetzt auf eine Eingabe (initiale Bandbelegung), jemals zum Stillstand kommen wird, das heißt die Berechnung terminiert.
dɑːtsˈuː bəvˈiːs ɛɾ, das das hˈaltɛpɾoːblˌeːm fyːɾ tˌuːrɪŋmaʃˈiːnən nˈɪçt lˈøːzbɑːɾ ɪst, dˈeː. hˈɑː., das ɛs nˈɪçt mˈøːklɪç ɪst, ˌalɡoːrˈɪtmɪʃ tsuː ɛntʃˈaɪdən, ˌɔp ˌaɪnə tˌuːrɪŋmaʃˈiːnə, ˈanɡəzˌɛtst aʊf ˌaɪnə ˈaɪnɡˌɑːbə ˌiːniːtiːˈɑːlə bˈandbəlˌeːɡʊŋ, jˈeːmɑːls tsʊm ʃtˈɪlstant kˈɔmən vˌɪɾt, das hˈaɪst diː bərˈɛçnʊŋ tˌɛɾmiːnˈiːɾt.