『undecidability』は英語で『undecidable』に接尾辞『-ity』を付けて作られた語で、『undecidable』は接頭辞『un-』と『decidable』からなる。『decide』はラテン語の『decidere』（切り分ける・決定する）に由来する。

『decidere』（ラテン語）→（古フランス語などを経て）中英語の『deciden／decide』→現代英語の『decide』。その後『decidable』に『un-』を付け『undecidable』が作られ、さらに『-ity』で『undecidability』が形成され、20世紀に論理学・計算機科学で多く使われるようになった。

元来は一般的な「決定できない」という意味だったが、20世紀に論理学・計算可能性の分野で「アルゴリズムによって決定できない」という専門的な意味に特化した。