paragraph_text: Entscheidungsproblem potražuje računalni program koji će uzeti kao ulaz opis formalnog jezika i matematičku tvrdnju u tom jeziku i vratiti kao izlaz "istina" ili "laž", ovisno o tome je li tvrdnja istinita ili lažna. Program ne treba opravdati svoj odgovor, niti pružiti dokaz, važno je jedino da uvijek da točan odgovor. Takav bi računalni program bio u mogućnosti odlučiti, na primjer, jesu li hipoteza kontinuuma ili Riemannova hipoteza istinite, čak i ako nije poznat dokaz ili opovrgavanje ovih tvrdnji.