Въпрос относно теорията на изчислимостта

[devguy]

Четох доста от лекциите и мисля че поразбрах повечето от материала но не ми стана ясно как стоят нещата в исторически аспект. Изчислими функции по Ербран-Гьодел, функции изчислими с машини на Тюринг, функции изчислими с машини на Пост, ламбда функции на Чърч, частично рекурсивни функции на Клини - всички те са се появили почти едновременно и незасивимо. Но какво е накарало толкова много хора да мислят по този въпрос? Кои са били актуалните проблеми по това време които са провокирали развитието на теорията на изчислимостта?

[Methuselah]

http://en.wikipedia.org/wiki/Hilbert%27s_problems

"Хилберт поставя няколко проблеми на математическата общност. Един от тях е построяването на пълна и непротиворечива математическа теория. Една теория е пълна, ако всяко твърдение може да се докаже чрез нея, че е или вярно или невярно. Непротиворечива означава, че не може едно твърдение да се докаже, че е едновременно вярно и невярно (това което видяхме в парадокса на Ръсел). Непротиворечивостта на една теория може да се докаже, като се създаде неин модел в друга теория, за която е доказано, че е непротиворечива. В крайна сметка, всичко се свежда до теорията на естествените числа (аритметика - т.е събиране, умножение), затова ако нейната непротиворечивост бъде доказана всички могат да си отдъхнат (иначе може в един хубав момент да се окаже, че всичко в което вярваме и ползваме всекидневно е фундаментално грешно…което не е много добре). Логиката се развива доста в началото на 20век точно за да се опита да докаже непротиворечивостта (и евентуално пълнотата) на аритметиката. Гьодел се появява с 2 теореми, които разклащат цялата математическа (и не само) научни общности. Прочетете теоремите му (които са доказани от него) и ще се уверите.
Теорема на Гьодел #1: Всяка система, която съдържа естествените числа (т.е е базирана на нея - както казахме всички основни дялове са базирани на ест. числа) и е непротиворечива е непълна (т.е съществува твърдение, което не е нито вярно, нито невярно - т.е не може да бъде доказано нито едното нито другото).
Добавянето на едно такова свойство би разширило системата, но тя пак ще остане надграждане на естествените числа, т.е ще съществува ново недоказуемо твърдение. Т.е даже безкрайно да добавяме аксиоми в теорията и тя да остава непротиворечива, никога няма да стане пълна.
Теорема на Гьодел #2: За всяка система съдържаща естествените числа, не може (в нея) да бъде доказана нейната непротиворечивост.
За да се докаже непротиворечивост на дадена система, трябва да се използва нейно разширение, което както се сещате не се знае дали е (не)противоречиво.

Математиците скоро се поуспокоили и се примирили с факта, че не могат да докажат непротиворечивостта на математиката, за това ще внимават повче като правят системи и ще стискат палци

С времето възникнал въпросът дали може машина да доказва факти от дадена система и да проверява тяхната вярност/невярност. След доуточняване на понятието алгоритъм е доказано, че твърдение от аритметиката не може да бъде проверено дали е вярно или грешно, но за геометрично твърдение това е възможно."

Горният цитат е от http://fmi.wikidot.com/ml00