Quando si sta dimostrando una lingua è decidibile, cosa stai facendo in modo efficace?

Question

Quando si stanno dimostrando una lingua è decidibile, cosa stai facendo in modo efficace?

Answer 1

Se si chiede come si fa, non sono sicuro, ma posso controllare.

Fondamentalmente, decidibile è la lingua per la quale si può costruire un algoritmo (cioè macchina di Turing) che fermare per qualsiasi ingresso finiti (con accettare o rifiutare l'ingresso). Indecidibile è la lingua che non è decidibile.

http://en.wikipedia.org/wiki/Recursive_language ... ma più sul tema può essere facilmente trovato. Su questo link c'è solo una rapida menzione del termine.

P.S. Così, quando si costruisce sopra algoritmo accennato, si sono fondamentalmente dimostrando che il linguaggio è decidibile.