Entscheidungsproblem vs. Unvollständigkeitssatz (miękkie pytanie)

Pierwszy termin jest używany przez Hilberta w swojej pracy z 1928 roku, ale w późniejszej pracy Gödela to samo nazywa się Unvollständigkeitssatz („twierdzenie o niekompletności”). Dla dzisiejszych niemieckich badaczy CS wydaje się, że częściej stosuje się Unvollständigkeitssatz , a Entscheidungsproblem („problem decyzyjny”) jest nadal rozumiany, ale niekoniecznie związany z das Halteproblem (który wydaje się bardziej powszechny po pracach Turinga nad automatami). Z drugiej strony, dla angielskich badaczy CS, Entscheidungsproblem jest zwykle jedynym znanym im słowem.

Uwaga : słowa nie są takie same i można argumentować, że na pytanie Hilberta dotyczące podejmowania decyzji udzielono przeczącej odpowiedzi w konkretnym przypadku w oświadczeniach Gödela o niekompletności , tak że niekompletność niszczy decyzję w ogóle.

Co ciekawe, patrząc na niemiecką Wikipedię, nie ma wpisu dla Entscheidungsproblem , ale jest taki dla Gödelscher Unvollständigkeitssatz , a wpis o Hilbercie używa Gödelscher Unvollständigkeitssatz . Patrząc na angielską Wikipedię, łatwo można znaleźć wpis dla Entscheidungsproblem .

Dlaczego Entscheidungsproblem nie jest już używany w języku niemieckim?

Te dwa słowa nie odnoszą się do tej samej rzeczy. Entscheidungsproblem Hilberta było pytaniem, czy istnieje algorytm, który decyduje o uniwersalnej prawdzie zdań logicznych pierwszego rzędu, na co odpowiedział negatywnie Turing w swoim słynnym artykule z 1936 r. „O liczbach obliczalnych, z zastosowaniem do Entscheidungsproblem ”. Słowo dosłownie oznacza problem decyzyjny . Zakładam, że słowo nie jest już używane, ponieważ odnosi się do problemu, który został rozwiązany. W języku angielskim może być jeszcze bardziej powszechny ze względu na jego wyraźne użycie w tytule artykułu Turinga.

Gödels Unvollständigkeitssatz jest jego twierdzeniem o niekompletności, stwierdzającym, że żadna spójna teoria arytmetyczna nie jest kompletna, w szczególności nie może udowodnić swojej spójności. To negatywnie odpowiedziało na inne pytanie Hilberta, a mianowicie. drugi z jego 23 słynnych problemów, który miał udowodnić spójność aksjomatów arytmetyki.