Decidability

/dɪˌsaɪ.dəˈbɪl.ɪ.ti/ · Noun · Development · Origin: 1936

Definitions

  1. A decision problem is decidable if there exists an algorithm that always halts and correctly answers yes or no for every input. Undecidable problems, like the halting problem or the Entscheidungsproblem, have no such algorithm.

    In plain English: Whether a yes-or-no question about programs or math can always be answered by a computer that doesn't run forever.

    Example: "Type checking in most languages is decidable — but add enough dependent types and you can make it undecidable."

Related Terms