Неизрачунљиве функције: разумевање граница израчунавања

У теорији израчунљивости, функција се назива неизрачунљивом ако се не може израчунати било којим алгоритмом. Другим речима, не постоји процедура која се може применити на улазне податке да би се произвео излаз функције.ӕӕ Пример неизрачунаве функције је проблем заустављања, који пита да ли ће се дати програм на крају зауставити (престати да ради) или ће наставити да ради на неодређено време. Ова функција је неизрачунава јер не постоји општи алгоритам који може да одреди да ли ће се дати програм зауставити или не.ӕӕДруги примери неизрачунавих функција укључују функцију Буси Беавер, која пита колико корака ће дата Тјурингова машина предузети пре него што се заустави, и Ентсцхеидунгспроблем, који поставља питање да ли је дати формални систем конзистентан или недоследан. Ове функције су такође неизрачунаве јер се не могу израчунати никаквим алгоритмом.ӕӕ Укратко, неизрачунаве функције су функције које се не могу израчунати никаквим алгоритмом и често се користе да покажу ограничења израчунавања и важност теорије сложености рачунара.