Undecidability

существительное

1. неразрешимость; неопределимость; нерешаемость

Состояние или свойство, при котором что-либо невозможно окончательно решить или определить; в математике и информатике — отсутствие общего алгоритма, способного решить каждую задачу в рамках определенного класса.

algorithmic undecidability — алгоритмическая неразрешимость
undecidability of the halting problem — неразрешимость проблемы остановки
proof of undecidability — доказательство неразрешимости
logical undecidability — логическая неразрешимость
undecidability of a formal system — неразрешимость формальной системы
Turing proved the undecidability of this problem. — Тьюринг доказал неразрешимость этой проблемы.
Gödel's theorems on undecidability — теоремы Гёделя о неразрешимости

Syn: unsolvability, indeterminability, unresolvability, indecidability

Слово образовано от английского глагола ‘decide’ (решать) с добавлением отрицательной приставки ‘un-’ (не-) и суффикса ‘-ability’ (способность, свойство). Термин прочно закрепился в англоязычной научной литературе (особенно в Великобритании и США) в 1930-х годах благодаря трудам Алана Тьюринга и Курта Гёделя, став ключевым понятием в математической логике и компьютерных науках для обозначения алгоритмической неразрешимости определенных проблем.

Прочие фразы и выражения

undecidability theorem — теорема о неразрешимости; теорема неразрешимости
essential undecidability — существенная неразрешимость; неотъемлемая неразрешимость

Однокоренные слова

decision — решение, определение, решимость, решительность
decisive — решающий, решительный, окончательный, убедительный, имеющий решающее значение
decisively — окончательно, убедительно
indecision — нерешительность, колебание
indecisive — нерешительный, неокончательный, нерешающий, колеблющийся, неопределенный
decide — решать, решаться, принимать решение, рассудить, постановлять, вознамериваться
decidable — разрешимый
undecidable — неразрешимый