Omejitve računalnikov

Neizračunljivi problemi

Problemi, za katere ne obstajajo algoritmi in jih posledično ni moč realizirati s Turingovim strojem.

Problem ustavljanja

Algoritma, ki nam bi povedal, ali se bo stroj po končnem številu korakov ustavil, ni mogoče narediti; torej se ga ne da rešiti s poljubnim Turingovim strojem. Dokaz temelji na postopku diagonalizacije (Georg Cantor).

Neobvladljivi problemi

Problemi, ki so sicer izračunljivi (se končajo po končnem številu korakov), vendar jih ni mogoče rešiti zaradi omejenega pomnilnika in/ali omejenega časa.

NP-polni problemi

NP = nedeterministično polinomski

sem spadajo vsi problemi, za katere lahko sestavimo polinomski algoritem na nedeterminističnem Turingovem stroju.

P

vsi problemi, za katere lahko sestavimo polinomski algoritem na determinističnem Turingovem stroju ()

NP-polni

posebna podmnožica NP; za vse probleme iz te množice je značilno, da so vsi polinomski ali pa nobeden - če bi dokazali, da se da sestaviti algoritem na determinističnem Turingovem stroju za enega od njih, bi pomenilo, da je možno sestaviti tak algoritem tudi za vse ostale. Problem P1 je NP-poln takrat, ko ga lahko prevedemo na nek drug problem P2 iz množice NP-polnih, ali ko lahko nek problem P3 iz te množice prevedemo na P1. S težavo, kako dobimo prvi problem iz te množice, se je soočil Stephen Cook (Cookov izrek, 1971)

Fizikalne omejitve

Problem, ker računalniki niso neskončno hitri. Klub izjemnim pohitritvam v zadnjih letih (približno 50x na vsakih 10 let), najbrž tudi nikoli ne bodo. Zaradi počasnejšega povečevanja hitrosti je v zadnjem času pomembna pot postala uporaba paralelnega procesiranja. Vendar ta pristop ni uporaben pri vseh problemih. Bremermann je z uporabo kvantne fizike postavil hipotezo, da hitrost računanja (v kakršni koli fizični obliki) ne bo presegla 2*10^47 bitov informacije na kg mase na sekundo.