Entscheidungsproblem

problema della decisione

È il problema della decisione che pone la richiesta di esibire meccanicamente una procedura in grado di stabilire se una formula espressa in linguaggio formale nella teoria del primo ordine (enunciati e deduzione sulle loro conseguenze logiche in modo formale e meccanico) sia o meno un predicato (collegamento a uno o più elementi del dominio per la formazione di una frase) deducibile all’interno del sistema formale basato sul teorema della logica del primo ordine (sintesi e sintassi).

Questa teoria rientra nella teoria del linguaggio computazionale (definizione delle proprietà possedute da uno specifico linguaggio formale).