Fa dimostrabile == decidibile?

Question

In teoria calcolo sono i termini dimostrabili e decidibile intercambiabili? Cosa significano la stessa cosa?

Per esempio si vede spesso la domanda se qualcosa è dimostrabile indicato come un problema decisionale (Das Entscheidungsproblem).

Answer 1

Questi sono diversi. In realtà, essi si riferiscono a zone completamente diverse.

mezzi decidibili, che un problema di decisione può essere risolto per tutti i possibili ingressi di una macchina di Turing che mette fuori 'accettare' o 'respingere'.

mezzi dimostrabile, che una dichiarazione matematica può essere dimostrata con, beh, una dimostrazione matematica.

In realtà, non è possibile confrontare 'decidibile' e 'dimostrabile', come questi attributi si riferiscono a cose completamente diverse.