Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin de içinde bulunduğu pek çok bilim ve mühendislik dalını yakından ilgilendiren hesaplanabilirlik teorisi (computability theory) konusundaki problemlerden birisidir.

Problemi basitçe tanımlama gerekirse bir koşulun (ki biz buna karar ismini vereceğiz) sağlanıp sağlanamadığını evet-hayır şeklinde ikili olarak (duality) sorgulamaktır.

Örneğin x gibi bir sayının ikiye tam bölünüp bölünememesi bir karar problemidir.

Bir karar probleminin sonucunun bulunup bulunamayacağı belirliyse bu tip problemlere kararı mümkün problemler (kararlaştırılabilir problemler, decidable problems) denilmektedir. Örneğin bir sayının ikiye bölümünden kalanın 0 olup olmaması bu tipten bir problemdir. Ancak bazı problemler bu gruba girmez. Örneğin pi sayısının noktadan sonraki bütün hanelerinin bulunamsı gibi. Bu problemin çözülüp çözülemeyeceği belirsizdir. Dolayısıyla problem kararı mümkün problem sınıfından değildir.

Bilgisayar bilimleri mantığı ile konuya yaklaşacak olursak bir problemin algoritmik olarak gösterilmesi veya göterilememesi karar probleminin mümkün olup olmamasını belirlemektedir.

Örneğin durma problemi (halting problem) bu anlamda önemli kararı mümkün olmayan problemlerdendir (undecidable problems).

Bu anlamda kararı mümkün problemleri üç grupta incelemek mümkündür:

kararı mümkün problemler (decidable problems): Şayet algoritma bir özyineli küme (recursive set) ise çözümü mümkün problemdir

Kararı kısmen mümkün problemler (semidecidable, partially decidable, provable, solvable) : Şayet algoritma özyineli sayılabilir küme ise (recursively enumarable set) bu durumda algoritmaya çözümü kısmen mümkün problem ismi verilir

Kararı mümkün olmayan problemler (undecidable problems): kararı kısmen mümkün problemler de dahil olmak üzere şayet bir algoritma özyineli bir küme (recurise set) üretemiyorsa bu gruba dahil edilir.