Un problema di decisione che può essere risolto da un algoritmo che si ferma su tutti gli ingressi in un numero finito di passi. Associato lingua è chiamata una lingua decidibile.