Pergunta

In computation theory are the terms Provable and Decidable interchangable? Do they mean the same thing?

For example you often see the question whether something is provable referred to as a decision problem (Das Entscheidungsproblem).

Foi útil?

Solução

These are different. In fact, they refer to completely different areas.

Decidable means, that a decision problem can be solved for all possible inputs by a Turing machine, which puts out 'accept' or 'reject'.

Provable means, that a mathematical statement can be proven by, well, a mathematical proof.

In fact, you cannot compare 'decidable' and 'provable', as these attributes refer to completely different things.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top