制限された非決定性

ウィキペディア小見出し辞書

制限された非決定性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/29 08:54 UTC 版)

「非決定性チューリングマシン」の記事における「制限された非決定性」の解説

NTM は制限された非決定性を持つ。すなわち NTM がある入力テープ T について必ず停止するとき、有限のステップ数の後に停止するのであり、考えられる構成の数は有限である。