Проблем одлучивања — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 8:
Проучавања у теорији израчунљивости се обично базирају на проблемима одлучивања. У овом случају немам губитка у општости разматрања у односу на функцијске проблеме.
== Дефиниција ==
''Проблем одлучивања'' је произвољно да-не питање на бесконачном скупу улаза. Због овога, традиционално се проблеми одлучивања дефинишу у смислу скупа улаза за које проблем враћа одговор ДА. У овом смислу, проблем одлучивања је еквивалентан [[формални језик|формалном језику]].
Формално, '''проблем одлучивања''' је подскуп ''-{A}-'' природних бројева. Коришћењем [[Геделов број|Геделових бројева]], могуће је проучавати и друге скупове као формалне језике. Неформално, ''проблем'' се састоји у одређивању да ли је дати број у скупу.
Проблем одлучивања се назива '''одлучивим''' или '''ефективно решивим''' ако је ''-{A}-'' [[рекурзиван скуп]]. Проблем се назива '''парцијално одлучивим''', '''полуодлучивим''', '''решивим''', или '''доказивим''' ако је ''-{A}-'' [[рекурзивно пребројив скуп]]. Парцијално одлучиви проблеми и сви остали проблеми који нису одлучиви се називају '''неодлучивим'''.
[[Категорија:Логика]]
| |||