Черч-Тјурингова теза

Шаблон:Loš seminarski У теорији израчунљивости, Черч-Тјурингова теза (такође позната као Тјуринг-Черчова теза, Черч-Тјурингове претпоставке, Черчова теза, Черчова претпоставка и Тјурингова теза) је хипотеза ("теза") о природи израчунљивих функција. Једноставно речено, Черч-Тјурингова теза гласи да је функција на природним бројевима израчунљива у неформалном смислу (тј израчунљива од стране људског бића коришћењем метода оловке и папира, игноришући ограничења ресурса) ако и само ако је израчунљива Тјуринговом машином. Теза је добила име по америчком математичару Алонзу Черчу и британском математичару Алану Тјурингу.

Пре прецизног дефинисања израчунљивих функција, математичари често користе неформалан термин ефективно израчунљив да опишу функције које су за израчунљиве методама папира и оловке-. 1930-их, било је неколико независних покушаја да се формализује појам Израчунљивости:

• 1933, Аустријски-Амерички математичар Курт Гедел, са Жаком Ербраном, је направио дормалну дефиницију класа под називом општа рекурзивна функција. Класа општих рекурзивних функција је најмања класа функција (могуће са више од једног аргумента) која укључује константне функције, пројекте, функцију наследног, и који је затворен у сложеној функцији и рекурзији.
• 1936, Алонзо Черч је створио метод за дефинисање функција под називом Ламбда рачун. У оквиру ламбда рачуна он је дефинисао кодирање природних бројева под називом Черчови бројеви. Функција над природним бројевима се зове ламбда израчунљива ако се одговарајућа функција на Черчовим бројевима може представити у тајању ламбда рачуна.
• Такође 1936, пре проучавања Черчовог рада, Алан Тјуринг је створио теоретски модел за машине, који се сада зове Тјурингове машине, које се могу побринути за рачунање из улаза манипулацијом симбола на траци. С обзиром на одговарајуће кодирање природних бројева као секвенце симбола, функција природних бројева  се назива Тјуринг израчунљива ако неке Тјурингове машине израчунају одговарајућу функцију над кодираним природним бројевима.

Черч и Тјуринг су доказали да се ове три формално дефинисане класе израчунљивих функција поклапају: функција је ламбда израчуљива  ако и само ако је Тјуринг израчунљива и акко је опште рекурзивна. Ово је натерало математичаре и информатичаре да поверују да је концепт израчунљивости тачно окарактерисан овим трома еквивалентним процесима. Остали формални покушаји да се карактерише израчунљивост је касније ојачао снагу овог веровања (погледати испод).

С друге стране, Черч-Тјурингова теза наводи да су горе наведене три формално дефинисане класе израчинљивих функција поклапају са неформалном појмом ефикасно прорачунљиве функције. Пошто, као неформални појам, концепт ефективне предвидивости нема формалну дефиницију, теза, иако има скоро универзалну прихваћеност, не може бити формално доказана.

Од свог оснивања, варијације на основној тези су се појавиле, укључујући изјаве о томе шта ће моћи физички бити реализовано уз помоћ рачунара у нашем универзуму (физичка Черч-Тјуринг теза) и шта ће моћи бити ефикасно израчунато (Сложеност-теоријски Черч-Тјурингова теза). Ове варијације нису због Черча или Тјуринга, али проистичу из каснијег рада у теорији сложености и дигиталне физике. Теза има импликације за филозофију духа.

Искази у Черчовим и Тјуринговим речима

Џ. Б. Росер (1939) бави се појмом "ефективне израчунљивости" на следећи начин: "Јасно постојање ЦЦ и РЦ (Черчови је и Росерови докази) претпоставља прецизну дефиницију 'ефективног' 'Ефективни метод" се овде користи у веома посебном смислу методе сви кораци који су прецизно унапред одређени и који сигурно произведе одговор у коначном броју корака. „Такосе прилог-придев "ефективан"  користи у смислу "1А: производећи одлучујућег, убедљивог, или жељеног ефекта" и "способан да произведе резултат".

У наставку, речи "ефикасно израчунљив" ће значити "произведен од стране било ког интуитивног 'ефективног' значи уопште" и "ефективно подложан рачунању" ће значити "произведени од стране Тјурингове-машине или еквивалентног механичког уређаја". Тјурингова "дефиниција" дата у фусноти у својој 1939. докторирао тезу Системи логике базираних на редним бројевима под надзором Черча, су готово исти:

"† Ми ћемо користити израз" израчунљива функција ' да означимо функцију израчунату на машини, и пустимо ' ефективно израчунате 'да се односи на интуитивну идеју без посебне  идентификације са било којим од ових дефиниција. "

Теза може гласити као следеће:

Свака ефективно израчунљива функција је функција подлежна рачунању.

Тјуринг је то изјавио на овај начин:

"Констатовано је да је ..." функција је ефективно израчунљива ако се њене вредности могу наћи помоћу неког чисто механичког процеса. " Можемо узети дословно, схватајући да је чисто механички процес онај који може да се обавља помоћу машине ... доводи до ... идентификације израчунљивости † са ефективном предвидивошчу. "(† је фуснота изнад, Ибид.)

Историја

Један од важних проблема за логичаре 1930. био је Давид Хилбертов Entscheidungsproblem, која је затражила да ли је механички поступак за одвајање математичких истина од математичких неистина. Овој потрази је потребно да  појам "алгоритма" или "ефективне предвидивост" буду приковани, барем довољно добро за трагање за почетак. Али од самог почетка покушаја Алонза Черча је почела са дебатом која се наставља до данашњег дана. Да ли је појам "ефективне предвидивост" да буде (и) "аксиом или аксиоми" у аксиоматског систему, или (ии) само дефиниција да је "идентификовао" два или више предлога, или (иии) емпиријска хипотеза да се утврди посматрањем природних догађаја, или (ив) или само предлог зарад аргумента (односно "теза").

Период 1930—1952

У току студирања проблема, Черч и његов студент Стивен Клини увео је појам λ дефинисане функције, и они су били у стању да докажу да се неколико великих класа функција често срећу у теорији бројева λ-дефинисани. Расправа је почела када је Черч предложио да Гедел треба дефинисати "ефективно израчунљиве" функције као λ дефинисане функције. Гедел, међутим, није био убеђен и назвао предлог "темељно не задовољава". Уместо тога, у преписци са Черчом (ца 1934-5), Гедел је предложио акиоматизинг појам "ефективне предвидивости"; Заиста, 1935 у писму Клину, Черч је известио да:

"Његова [Геделов] једина идеја у то време била је да би то било могуће, у смислу ефикасне предвидивост као недефинисаног појма, да наведе скуп аксиома који би отеловљавали општеприхваћена својства овог појма, и да уради нешто на тој основи ".

Али Гедел није понудио даља упутства. На крају, он би предложио своју (примитивну) рекурзију, модификовану од стране Хербранда сугестију, коју је Гедел детаљисао у својим предавањима из 1934 Принстон НЈ(Клини и Росер преписали су белешке). Али "није мислио да две идеје могу на задовољавајући начин бити идентификоване " осим хеуристички ".

Даље, било је неопходно да се идентификују и докаже еквивалентност два појма ефикасне предвидивост. Опремљен ламбда-рачуном и "примитивном" рекурзијом, Стивен Клини уз помоћ Черча и Џ. Б. Росера производи доказе (1933, 1935) да покаже да су два рачуна еквивалентна. Черч накнадно измењује своје методе укључују употребу Хербранд-Гедел рекурзије, а затим је доказао (1936) да је Entscheidungsproblem нерешив: Не постоји уопштен "ефективнан обрачун" (метод, алгоритам) који може да одреди да ли су или не формуле у било којој рекурзији - или ламбда рачуну "важеће" (прецизније: нема методе да се покаже да добро формирана формула има "нормалнан облик").

Много година касније, у писму упућеном Дејвису (ца 1965), Гедел би признао да је "он био, у време ових [1934] предавања, уопште убеђен да његов концепт рекурзије чини све могуће рекурзије". По 1963-4 Гедел би одрекао Хербранд-Гедел рекурзију и λ-рачуницу у корист Тјурингове машине као дефиниције "алгоритма" или "механичког поступка" или "формалног система".

Хипотеза која је довела до природног закона ?: Крајем 1936 Алан Тјурингов рад (такође доказује да је Entscheidungsproblem нерешив) је досрављен усмено, али се још није појавио у штампи. С друге стране, Емил Постов рад 1936 се појавио и био сертификован независно од рада Тјуринговог рада. Пост се снажно не слаже са Черчовом "идентификацијом" ефективне израчунљивости са λ-рачуном и рекурзијом, наводећи:

"Заправо посао је већ урађен од стране Черча и других носи ову идентификацију знатно изван радне фазе хипотезе. Али да прикрије ову идентификацију под дефиницијом ... заслепљује нас на потребу њене непрекидне верификације."

Уместо тога, он сматра појам "ефективне предвидивости" као само "радна хипотеза" која може да се доведе  индукционим образложењем до "природно право", пре него "дефиницију или аксиом". Ову идеју је "оштро" критиковао Черч.

Тако је Пост у свом раду 1936 такође дисконтовао Курт Геделову сугестију Черчу 1934-5 да теза може бити изражена као аксиом или скуп аксиома.

Тјуринг додаје још једну дефиницију, Росер изједначава све три: У само кратком времену, Тјурингов рад 1936-37 "На израчунљивим бројева, са применом у Entscheidungsproblem" се појавио. У њој је навео још један појам "ефективне израчунљивости" са увођењем својих А-машина (сада познате као Тјурингова машина - апстрактан рачунарски модел). У доказу-скици додаје као "Прилог" у свој рад 1936-37 , Тјуринг је показао да су се класе функција дефинисана λ-рачуном и Тјурингова машина поклопиле. Черч је брзо препознао колико је убедљива Тјурингова анализа. У свом прегледу Тјуринговог рада рекао је да је јасно да је Тјурингова идеја "идентификација са ефикасности у обичном (не експлицитно дефинисаном) смислу евидентна одмах".

За неколико година (1939) Тјуринг би предложио, као Черч и Клини пре њега, да је његова формална дефиниција механичке израчунљивости био исправан. Тако, 1939. године, и Черч (1934) и Тјуринг (1939) су индивидуално предложили да њихови "формални системи" буду дефиниције "ефективне предвидивост"; нико није урамио њихове изјаве као тезу.

Росер (1939) је формално идентификовао три појма као дефиниције:

"Све три дефиниције су еквивалентне, тако да није битно која се користи."

Клини предлаже Черчову тезу : Ово је оставило отворен израз једне "тезе" Клинију. У свом раду 1943 Рекурзивни Предикати и квантификатори Клини је предложио своју "ТЕЗУ И":

"Ова хеуристичка чињеница [опште рекурзивне функције су ефикасно израчунате] ... довела је Черча да наведе следећу тезу (22). Иста теза је садржана у Тјуринговом опису рачунских машина (23).

"ТЕЗА И. Свака ефективно израчунљива функција (ефективно одлучив предикат) је опште рекурзивна [Клинијев курзив]

"Од прецизне математичке дефиниције појма ефективно израчунљиве (ефективно одлучиве) је хтео, можемо искористити ову тезу ... као дефиницију тога ..."

"(²²) референце Черча 1936

"(²³) референце Тјуринга 1936–7

Клини иде у белешци да :

"... Та теза има карактер једне хипотезе тачке наглашене од стране Поста и Черча (24). Ако узмемо у обзир и његову тезу обрнутог тврђења као дефиницију, онда је хипотеза је хипотеза о примени математичке теорије развијена из дефиниције. За прихватање хипотезе, постоје, као што смо предложили, прилично уверљиви разлози. "

.. "(24) референце Поста1936 Постова и Черчова формална дефиниција у теорији редних бројева, Фонд, Математика вол 28 (1936) пп.11-21 (види реф #2, Дејвис 1965: 286).

Клинијева Черч-Тјурингова Теза: Неколико година касније (1952) Клини би отворено именовао, бранио, и изражавао две "тезе", а затим их "идентификовао" (показао једнакост) употребом његове Теореме ХХХ:

"Хеуристички докази и други разлози довели су Черча 1936 да предложи следеће тезе.

ТЕЗА И. Свака ефективно израчунљива функција (ефективно одлучив предикат) је опште рекурзивна.

Теорема ХХХ: "Следеће класе парцијалних функција су коекстензивне, тј имају исте чланове: (а) парцијалне рекурзивне функције, (б) израчунљиве функције ...". Тјурингова теза: "Тјурингова теза да свака функција коју би требало природно сматрати за израчунљиву је израчунљива под својом дефиницијом, односно једна од његових машина, је еквивалентна тези Черча од стране Теореме ХХХ."

Каснији развоји

Покушај да се разуме појам "ефективне израчунљивости" је боље водио Робин Ганди (Тјурингов ученик и пријатељ) 1980. да анализира прорачун машине (као супротност људској-израчунљивости поступило од Тјурингове машине). Гандијева радозналост у вези, и анализи, "ћелијског аутомата", "Конвејеве игре живота", "паралелизма" и "кристалног аутомата" га је навело да предложи четири "принципа (или ограничења) ... која су тврдио је, било која машина мора задовољити. " Његов најважнији четврти, "принцип каузалитета" се заснива на "коначној брзини простирања ефеката и сигнала; савремена физика одбацује могућност тренутног деловања на даљину". Од ових принципа и неких додатних ограничења- (1а) доња граница на линеарној димензији било ког дела, (1б) горња граница брзина распростирања (брзина светлости), (2) дискретан напредак машине, и (3) детерминистичко понашање-да производи теорему која "Оно што се може израчунати помоћу уређаја задовољава принципе 1-4 је израчунљиво.".

У касним 1990-им Вилфред Зиг анализирао јњ Тјурингове и Гандијеве појмове "ефективне предвидивост" са намером да "оштрења неформалног појма, формулисање његове опште карактеристике аксиоматски, и истраживању аксиоматског оквира". У свом раду 1997. и 2002. године Зиг представља низ ограничења на понашање једног рачунала- "агент људског рачунарства који наставља механички". Ова ограничења своде на:

• "(Б.1) (Коначности) Постоји фиксно ограничење на броју симболичних конфигурација које рачунало може одмах препознати.
• "(Б.2) (Коначности) Постоји фиксно ограничење на броју унутрашњих стања које могу бити у рачуналу.
• "(Л.1) (Локалитет) Рачунар може променити само елементе посматране симболичке конфигурације.
• "(Л.2) (Локалитет) Рачунар може померити пажњу са једне симболичке конфигурације на другу, али нова посматрана конфигурација мора бити унутар ограничене удаљености од непосредне претходно посматране конфигурације.
• "(Д) (Одлучност) Непосредно препознатљива (суб-) Конфигурација одлучује једнозначно следећи корак израчунавања (и ИД [тренутни опис])"; Другачије речено: "унутрашње стање А рачунало заједно са посматраном конфигурацијом фиксира јединствен следећи корак рачунања и следеће унутрашње стање."

Питање остаје у активној дискусији у оквиру академске заједнице.

Теза као дефиниција

Теза може да се посматра као ништа осим обичне математичке дефиниције. Коментари од Гедела на тему указују на овај став, нпр "основна тачна дефиниција механичке израчунљивости је утврђена ван сваке сумње од стране Тјуринга". Случај за гледање тезе као ништа више од дефиниције је експлицитно створио Роберт И. Соаре у којој се такође тврди да није ништа мање вероватно да ће Тјурингова дефиниција бити тачна него ипсилон-делта дефиниција непрекидне функције.

Успех тезе

Остали формализми (осим рекурзије је λ-рачун, и Тјурингова машина) су предложени за описивање ефикасне предвидивости / израчунљивости. Стивен Клини (1952) додаје на листу функције "Процењиви у систем С1" Курт Гедела 1936, и Емил Постових (1943, 1946) "канонских [такође зване нормалним] система". У 1950. Хао Ванг и Мартин Дејвис у великој мери су поједноставили модел Тјурингове машине са једном траком (види пост-Тјурингову Машине). Марвин Мински је проширио модел на две или више траке и увелико поједностављена трака у "горе-доле шалтерима", које су Мелзак и Ламбек даље еволуирали у оно што је сада познато као модел бројач машине. У касним 1960-им и раним 1970-им истраживачи су проширили модел бројач машине у Регистар машину, блиски рођак са модерним појмом рачунара. Остали модели укључују Комбинацијску логику и Марков алгоритме. Гуревич додаје модел Показивач машине Колмогорова и Успенског (1953, 1958) : "... они су само хтели да ... увере себе да не постоји начин да се продужи појам израчунљиве функције."

Сви ови доприноси укључују доказе да су модели су рачунски еквивалентни Тјуринговој машини; такви модели су, како је речено Тјуринг потпуни. Зато што су сви ови различити покушаји формализовања концепта "ефикасна предвидивост / израчунљивост" дале су еквивалентне резултате, сада се генерално претпоставља да је Черч-Тјурингова теза тачна. У ствари, Гедел (1936) је предложио нешто јаче од овога; он је приметио да постоји нешто "апсолутно" о концепту "Процењиви у С1":

"То може да се покаже да је функција која је израчунљива ['Процењива'] у једном од система Си, или чак у систему трансфинит типа, већ израчунљива [Процењива] у С1. Тако је концепт" за израчунавање "['Процењиви '] у извесном смислу одређеном' апсолутно ', док су практично сви остали познати математички концепти (нпр доказати, дефинисати, итд) зависи доста битно на систему којима су дефинисане "

Неформална употреба у доказима

Докази у теорији израчунљивости често позивају на Черч-Тјурингову тезу на неформалан начин да се успостави израчунљива функција избегавајући (често веома дуго) детаље који ће бити укључени у ригорозан, формални доказ. Да се утврди да је функција израчунљива Тјуринговом машином, обично се сматра довољним да се добије неформалан енглески опис како се функција може ефикасно израчунати, а затим закључити "На основу Черч-Тјурингове тезе" да је функција Тјуринг израчунљива (еквивалентно парцијална рекурзивна).

Дирк ван Дален (у Габаију 2001:284) даје следећи пример зарад илустрације ове неформалне употребе Черч-Тјурингове тезе:

ПРИМЕР: Сваки бесконачни РЕ скуп садржи бесконачан рекурзивни скуп.

Доказ: Нека је бесконачно Ре. Наводимо елементе А ефикасно, n₀, n₁, n₂, n₃, ...

Из овог списка можемо издвојити већу подлисту: стави m₀=n₀, после коначно много корака можемо наћи n_k такво да n_k > m₀, стави m₁=n_k. Понављамо ову процедуру да нађемо m₂ > m₁, итд ово даје ефикасан листинг на подскуп B={m₀,m₁,m₂,...} од А, са имовином m_i < m_i+1.

Тврдња. B је одлучив.Јер, да би тестирали  k у B морамо проверити да ли јеk=m_i за неко i. Како се редослед m_i's  повећава морамо производити највише k+1 елемената листе и поредити их са k. Ако ни један од њих није једнак k, онда k није у B. Док је овај тест ефективан, B је одлучив и, на основу Черчове тезе, рекурзиван.

(Нагласак додат). Да би направио горњи пример потпуно ригорозним, један би морао да пажљиво изгради Тјурингове Машине, или λ-функцију, или пажљиво позвати рекурзије аксиоме, или у најбољем случају, мудро позивати различите теореме теорије израчунљивости. Али пошто теоретичари израчунљивости сматрају да Тјурингова израчунљивост правилно снима оно што се може ефикасно израчунати, и зато ефикасна процедура је написана на енглеском језику за одлучивање у скупу В,  теоретичар израчунљивости прихвата то као доказ да је скуп заиста рекурзиван.

Као правило, Черч-Тјурингова теза да треба применити само да се поједноставе докази у случајевима у којима би писац био у стању да, и очекује да ће читаоци такође да буду у стању да, лако (али не нужно без досаде) производећи ригорозне доказе ако неко од њих захтева.

Варијације

Успех Черч-Тјурингове тезе затражио је да се варијације тезе предложе. На пример, физичка Черч-Тјурингова теза (ФЧТТ) наводи:

"Све физички израчунљиве функције су Тјуринг-израчунљиве"

Черч-Тјурингова теза ништа не говори о ефикасности којом један модел обрачуна може симулирати други. Доказано је, на пример, да само (са више трака) универзална Тјурингова машина трпи фактор логаритамског успоравања за симулирање било које Тјурингове Машине. Такав резултат је показао уопште за произвољан, али и разуман модел израчунљивости. Варијација на Черч-Тјуринговој тези да се бави овим питањем је Теза изводљивости или (Класична) Сложено-теоријски Черч-Тјурингова теза (СТЧТ), која није последица Черча или Тјуринга, већ је реализована постепено у развоју теорије комплексности. У њој се наводи:

"А пробабилистичка Тјурингова машина може ефикасно симулирати било који реалан модел израчунавања."

Реч "ефикасно" овде значи до полиномског смањења времена. Ова теза је првобитно названа Израчунљива Сложено-теоријски Черч-Тјурингова теза од Етана Бернштајна и Умеша Вазиранија (1997). Комплексно-теоријска Черч-Тјурингова теза, онда, претпоставља да ће сви разумни „модели израчунљивости дати исте класе проблема који може да се израчуна на полиномијалном времену. Под претпоставком да пробабилистички полиномијално време (БПП) једнак детерминистичком полиномијалном времену (п), реч 'вероватноће' је опционо у сложено-теоријски Черч-Тјуринговој тези. Слична теза, названа Теза Инваријантности, представио је Цес Ф. Слот и Петер ван Емде Боас. Она каже: "Разумне" машине се могу симулирати међусобно унутар полиномијално ограниченом ваздушном у времену и константнимм горњим фактором  у простору. Теза се првобитно појавио у новинама на СТОЦу'84, који су биле прве новине да покажу да је полиномијално време горњег и константан-простор горњег могу бити истовремено постигнута за симулацију РАМ на Тјуринговој машини.

Ако је БКП приказан да буде строг надскуп БПП, то би поништило Сложено-теоријску Черч-Тјурингову тезу. Другим речима, не би било ефикасних квантних алгоритма који обављају послове који немају ефикасни пробабилистички алгоритми. То не би, међутим, могло да поништи првобитну Черч-Тјурингову тезу, јер квантни рачунар може увек да се симулира Тјуринговом машином, али би поништило класичну Сложено-теоријску Черч-Тјурингову тезу за ефикасност разлога. Сходно томе, Квантно Сложено-теоријска Черч-Тјурингова теза гласи:

"Квантна Тјурингова машина може ефикасно симулирати било који реалан модел израчунљивости."

Јуџин Ебербах и Петер Вегнер тврде да се Черч-Тјурингова теза понекад тумачи превише широко, наводећи "ширу тврдњу да алгоритми управо заузму оно што се може израчунати је неважеће". Они тврде да облици израчунавања нису заробљени од стране тезе су релевантни данас, термини који називају супер Тјуринг израчунљив.

Филозофске импликације

Филозофи су тумачили Черч-Тјурингову тезу да имају импликације за филозофију духа; Међутим, многи од филозофских тумачења тезе укључују основне неспоразуме на изјаве теза. Б Џек Копленд каже да је отворено емпиријско питање да ли постоје стварни детерминистички физички процеси који, на дуже стазе, заобилазе симулацију Тјуринговом машином; Осим тога, он тврди да је отворено емпиријско питање да ли су неки такви процеси укључени у рад људског мозга. Постоје нека важна отворена питања која покривају однос између Черч-Тјурингове тезе и физике, као и могућност хиперизрачунљивости. Када се примени на физици, теза има неколико могућих значења:

1. Универзум је еквивалентан Тјуринговом машином; дакле, израчунљивост не-рекурзивне функције је физички немогуће. Ово је назива Јака Черч-Тјурингова теза и представља темељ дигиталне физике.
2. Универзум није еквивалентан Тјуринговом машином (тј закони физике нису Тјуринг-израчунљиви), али неизрачунљиви физички догађаји нису "харнесејбл" за изградњу хиперрачунара. На пример, универзум у којем физика укључује реалне бројеве, за разлику од израчунљивости реалних бројева, можда спадају у ову категорију. Претпоставка да неизрачунљиви физички догађаји нису "харнесејбл" су изазвали, међутим, предложене рачунарске процесе који користе квантну случајност заједно са рачунарским машинама да сакрију рачунарске кораке универзалне Тјурингове машине са Тјуринг-неизрачунљивим запаљивим обрасцима.
3. Универзум је хиперрачунар, а могуће је изградити физичке уређаје да искористе ову особину и израчунају не-рекурзивне функције. На пример, то је отворено питање да ли су сви Квантномеханички догађаји Тјуринг-израчунљиви, иако је познато да ригорозни модели као што су квантна Тјуринг машина су еквивалентни детерминистичким Тјуринговим машинама. (Они нису нужно ефикасно еквивалентни; види горе.) Џон Лукас и Роџер Пенроуз су сугерисали да људски ум може бити резултат неке врсте квантно-механички појачане, "не-алгоритмическе" израчунљивости, иако нема научних доказа за овај предлог.

Постоје многе друге техничке могућности које спадају изван или између ове три категорије, али они служе да илуструју опсег појма.

Неизрачунљиве функције

Један формално може дефинисати функције које нису израчунљиве. Добро познати пример такве функције је заузетог дабра. Ова функција узима улаз н и враћа највећи број симбола које Тјурингова машина са н стања може да штампа пре заустављања, када се ради без улаза. Проналажење горње границе на прометној функцији даброва је еквивалентна решавању халтинг проблема, проблем познат бити нерешив Тјуринговим машинама. Пошто заузет дабар не може да се израчуна Тјуринговим машинама, Черч-Тјурингова теза каже да ова функција не могу бити ефикасно израчунљива било којом методом.

Неколико рачунарских модела омогућавају израчунавање (Черч-Тјуринг) неизрачунљивих функција. Они су познати као хиперрачунари. Марко Бургин тврди да супер рекурзивни алгоритми, као што су индуктивне Тјурингове машине оповргну Черч-Тјурингову тезу. Његов аргумент почива на дефиницији алгоритма шире од обичне, тако да неизрачунљиве функције добијене из неких индуктивних Тјуринг машина се зову израчунљиве. Ово тумачење Черч-Тјурингове тезе разликује се од тумачења обично прихваћених у теорији израчунљивости, горе наведено. Аргумент да су супер рекурзивни алгоритми заиста алгорими у смислу Черч-Тјурингове тезе није нашао широко прихватање у Израчунљивој истраживачкој заједници.

Др Селим Г Акл са Универзитета Квинс (Школа рачунања) оспорава да је Черч-Тјурингова теза доказиво нетачно заснована на низу функција које су израчунљиве али генерално сматра да буду неизрачунљиве.

Види још

• Апстрактна машина
• Черчова теза у конструктивној математици
• Логика израчунљивости
• Теорија израчунљивости
• Одлучивост
• Историја Черч-Тјурингове тезе
• Хиперрачунар
• Модел израчунљивости
• Супер рекурзивни алгоритам
• Черч-Тјуринг-Немачки принцип, који наводи да сваки физички процес може бити симулиран универзалном рачунарском машином
• Стохастика
• Monte Carlo method

Фусноте

1. Rabin, Michael O. (June 2012). Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View.
2. Church 1934:90 footnote in Davis 1952
3. Turing 1936–7 in Davis 1952:149
4. Rosser 1939 in Davis 1965:225
5. Merriam Webster's Ninth New Collegiate Dictionary
6. "See also" Merriam-Webster's Online Dictionary, 11th Edition (accessed July 26, 2014), which also gives these definitions for "effective" -- the first ["producing a decided, decisive, or desired effect"] as the definition for sense "1a" of the word "effective", and the second ["capable of producing a result"] as part of the "Synonym Discussion of EFFECTIVE" there, (in the introductory part, where it summarizes the similarities between the meanings of the words "effective", "effectual", "efficient", and "efficacious").
7. A. M. Turing (1939), Systems of Logic Based on Ordinals (Ph.D. thesis). Princeton University. стр. 8.
8. Gandy (Gandy 1980 in Barwise 1980:123) states it this way: What is effectively calculable is computable. He calls this "Church's Thesis", a peculiar choice of moniker.
9. Davis's commentary before Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:88. Church uses the words "effective calculability" on pp. 100ff.
10. In his review of Church's Thesis after 70 Years edited by Adam Olszewski et al. 2006, Peter Smith's criticism of a paper by Muraswski and Wolenski suggests 4 "lines" re the status of the Church–Turing Thesis: (1) empirical hypothesis (2) axiom or theorem, (3) definition, (4) explication. But Smith opines that (4) is indistinguishable from (3), cf Smith (July 11, 2007) Church's Thesis after 70 Years at http://www.logicmatters.net/resources/pdfs/CTT.pdf
11. cf footnote 3 in Church 1936 An Unsolvable Problem of Elementary Number Theory in Davis 1965:89
12. Dawson 1997:99
13. Sieg 1997:160
14. Sieg 1997:160 quoting from the 1935 letter written by Church to Kleene, cf Footnote 3 in Gödel 1934 in Davis 1965:44
15. cf Church 1936 in Davis 1965:105ff
16. Davis's commentary before Gödel 1934 in Davis 1965:40
17. For a detailed discussion of Gödel's adoption of Turing's machines as models of computation, see Shagrir date TBD at http://edelstein.huji.ac.il/staff/shagrir/papers/Goedel_on_Turing_on_Computability.pdf
18. Turing 1937
19. cf. Editor's footnote to Post 1936 Finite Combinatory Process. Formulation I. at Davis 1965:289.
20. Post 1936 in Davis 1965:291 footnote 8
21. Post 1936 in Davis 1952:291
22. Sieg 1997:171 and 176–7
23. Turing 1936–7 in Davis 1965:263ff
24. Church 1937
25. Turing 1939 in Davis:160
26. cf. Church 1934 in Davis 1965:100, also Turing 1939 in Davis 1965:160
27. italics added, Rosser 1939 in Davis 1965:226
28. An archaic usage of Kleene et al. to distinguish Gödel's (1931) "rekursiv" (a few years later named primitive recursion by Rózsa Péter (cf Gandy 1994 in Herken 1994–5:68)) from Herbrand–Gödel's recursion of 1934 i.e. primitive recursion equipped with the additional mu operator; nowadays mu-recursion is called, simply, "recursion".
29. Kleene 1943 in Davis 1965:274
30. Kleene 1952:300
31. Kleene 1952:376
32. Gandy 1980 in Barwise 1980:123ff)
33. Gandy 1980 in Barwise 1980:135
34. Gandy 1980 in Barwise:126
35. (Sieg 1998–9 in Sieg–Somner–Talcott 2002:390ff; also Sieg 1997:154ff)
36. In a footnote Sieg breaks Post's 1936 (B) into (B.1) and (B.2) and (L) into (L.1) and (L.2) and describes (D) differently. With respect to his proposed Gandy machine he later adds LC.1, LC.2, GA.1 and GA.2. These are complicated; see Sieg 1998–9 in Sieg–Somner–Talcott 2002:390ff.
37. A collection of papers can be found at Church's Thesis after 70 Years edited by Adam Olszewski et al. 2006. Also a review of this collection by Peter Smith (July 11, 2007) Church's Thesis after 70 Years at http://www.logicmatters.net/resources/pdfs/CTT.pdf
38. See also Hodges, Andrew (2005). "Did Church and Turing Have a Thesis about Machines?" (PDF). Archived from the original on July 27, 2014. Retrieved July 27, 2014.
39. Gödel, K. [193?], "Undecidable Diophantine Propositions", in Collected Works, III. стр. 168.
40. R. I. Soare, 1996, Computability and Recursion, Bulletin of Symbolic Logic v. 2 pp. 284–321.
41. Kleene 1952:320
42. Gurevich 1988:2

• translation of Gödel (1936) by Davis in The Undecidable pp. 83, differing in the use of the word 'reckonable' in the translation in Kleene (1952). стр. 321.
• Horsten in Olszewski 2006:256
• Gabbay 2001:284
• Piccinini 2007:101 "Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy". doi:10.1007/s11229-005-0194-z. in Synthese (2007) 154:97–120.
• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press. 2009. ISBN 978-0-521-42426-4., section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
• http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
• Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press. 2007. ISBN 978-0-19-857049-3. стр. 5–6.
• Peter van Emde Boas's, Machine Models and Simulations, in Handbook of Theoretical Computer Science A, Elsevier. . (1990). стр. 5.
• C. Slot, P. van Emde Boas, On tape versus core: an application of space efficient perfect hash functions to the invariance of space, STOC, December 1984
• Eberbach and Wegner, 2003
• In particular, see the numerous examples (of errors, of misappropriation of the thesis) at the entry in the Stanford Encyclopedia of Philosophy. For a good place to encounter original papers see David J. Chalmers, ed. 2002, Philosophy of Mind: Classical and Contemporary Readings, Oxford University Press, New York.
• B. Jack Copeland, Computation in Luciano Floridi (ed.), The Blackwell guide to the philosophy of computing and information, Wiley-Blackwell. 2004. ISBN 978-0-631-22919-3. стр. 15.
• Michael Fiske, "Turing Incomputable Computation" in Turing-100 proceedings, The Alan Turing Centenary. http://www.easychair.org/publications/?page=1303694832.
• cf his subchapter "The Church–Turing Thesis" (p. 47–49) in his chapter "Algorithms and Turing machines" in his 1990 (2nd edition) Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, Oxford UK. Also his a final chapter titled "Where lies the physics of mind?" where, in a subsection he describes "The non-algorithmic nature of mathematical insight" (p. 416–8).
• Super-Recursive Algorithms (Monographs in Computer Science), Springer. 2005. ISBN 978-0-387-95569-8.
• http://research.cs.queensu.ca/Parallel/projects.html#Current

Литература

• Barwise, Jon, H. J. Keisler, and K. Kunen, Editors, The Kleene Symposium, 426 pages, North-Holland Publishing Company, Amsterdam. 1980. ISBN 978-0-444-85345-5.
• Ben-Amram, A.M. (2005). "The Church-Turing Thesis and its Look-Alikes". SIGACT News 36 (3): 113–116. doi:10.1145/1086649.1086651.
• Bernstein, E; Vazirani, U. (1997). "Quantum complexity theory". SIAM Journal on Computing 26 (5): 1411–1473. doidoi:10.1137/S0097539796300921.
• Blass, Andreas; Yuri Gurevich (2003). "Algorithms: A Quest for Absolute Definitions" (PDF). Bulletin of European Association for Theoretical Computer Science (81).
• Burgin, Mark (2005). "Super-recursive algorithms". Monographs in computer science. Springer. ISBN 0-387-95569-0.
• Church, Alonzo (1932). "A set of Postulates for the Foundation of Logic". Annals of Mathematics 33 (2): 346–366. doidoi:10.2307/1968337. JSTOR 1968337.
• Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". American Journal of Mathematics 58 (58): 345–363. doidoi:10.2307/2371045. JSTOR 2371045.
• Church, Alonzo (1936). "A Note on the Entscheidungsproblem". Journal of Symbolic Logic (1): 40–41. doidoi:10.2307/2269326.
• Church, Alonzo (1937). "Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem". Journal of Symbolic Logic (2): 42–43. doidoi:10.2307/2268810.
• Church, Alonzo (1941). The Calculi of Lambda-Conversion. Princeton: Princeton University Press.
• Cooper, S. B.; Odifreddi, P. (2003). "Incomputability in Nature". In S. B. Cooper & S. S. Goncharov. Computability and Models: Perspectives East and West. Kluwer Academic/Plenum Publishers. стр. 137–160.
• Davis, Martin, ed. (1965). The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems And Computable Functions. New York: Raven Press. Includes original papers by Gödel, Church, Turing, Rosser, Kleene, and Post mentioned in this section.
• Eberbach, E.; Wegner, P. (October 2003). "Beyond Turing Machines". Bulletin of the European Association for Theoretical Computer Science (81): 279–304.
• Gabbay, D.M. (2001). Handbook of Philosophical Logic 1 (2nd ed.).
• Gandy, Robin (1980). "Church's Thesis and the Principles for Mechanisms". In H.J. Barwise, H.J. Keisler, and K. Kunen. The Kleene Symposium. North-Holland Publishing Company. стр. 123–148.
• Gandy, Robin (1994–5). Rolf Herken, ed. The universal Turing Machine: A Half-Century Survey. New York: Wien Springer–Verlag. стр. 51ff. ISBN 3-211-82637-8. Check date values in: |date= (help)
• Gödel, Kurt (1965) [1934]. "On Undecidable Propositions of Formal Mathematical Systems". In Davis, M. The Undecidable. Kleene and Rosser (lecture note-takers); Institute for Advanced Study (lecture sponsor). New York: Raven Press.
• Gödel, Kurt (1936). "On The Length of Proofs". Ergenbnisse eines mathematishen Kolloquiums (in German) (Heft) (7): 23–24. Cited by Kleene (1952) as "Über die Lāange von Beweisen", in Ergebnisse eines math. Koll, etc.
• Gurevich, Yuri (June 1988). "On Kolmogorov Machines and Related Issues". Bulletin of European Association for Theoretical Computer Science (35): 71–82.
• Gurevich, Yuri (July 2000). "Sequential Abstract State Machines Capture Sequential Algorithms" (PDF). ACM Transactions on Computational Logic 1 (1): 77–111. doidoi:10.1145/343369.343384.
• Herbrand, Jacques (1932). "Sur la non-contradiction de l'arithmétique". Journal fur die reine und angewandte Mathematik (166): 1–8.
• Hofstadter, Douglas R.. "Chapter XVII: Church, Turing, Tarski, and Others". Gödel, Escher, Bach: an Eternal Golden Braid.
• Kleene, Stephen Cole (1935). "A Theory of Positive Integers in Formal Logic". American Journal of Mathematics 57 (57): 153–173 & 219–244. doidoi:10.2307/2372027. JSTOR 2372027.
• Kleene, Stephen Cole (1936). "Lambda-Definability and Recursiveness". Duke Mathematical Journal (2): 340–353. doidoi:10.1215/s0012-7094-36-00227-2.
• Kleene, Stephen Cole (1943). "Recursive Predicates and Quantifiers". American Mathematical Society Transactions (Transactions of the American Mathematical Society, Vol. 53, No. 1) 54 (1): 41–73. doidoi:10.2307/1990131. JSTOR 1990131. Reprinted in The Undecidable. стр. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" ( pp. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis" (Kleene 1952:317) (i.e., the Church thesis).
• Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. OCLC 523942.
• Knuth, Donald (1973). The Art of Computer Programming. 1/Fundamental Algorithms (2nd ed.). Addison–Wesley.
• Kugel, Peter (November 2005). "Communications of the ACM". It's time to think outside the computational box 48 (11).
• Lewis, H.R.; Papadimitriou, C.H. (1998). Elements of the Theory of Computation. Upper Saddle River, NJ, USA: Prentice-Hall.
• Manna, Zohar (1974) [2003]. Mathematical Theory of Computation. Dover. ISBN 978-0-486-43238-0.
• Markov, A.A. (1960) [1954]. "The Theory of Algorithms". American Mathematical Society Translations 2 (15): 1–14.
• Olszewski, Adam (2006). Church's Thesis After 70 Years.
• Pour-El, M.B.; Richards, J.I. (1989). Computability in Analysis and Physics. Springer Verlag.
• Rosser, J. B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 4, No. 2) 4 (2): 53–60. doidoi:10.2307/2269059. JSTOR 2269059.
• Sieg, Wilfried, Richard Sommer, and Carolyn Talcott (eds.), 2002, Reflections on the Foundations of Mathematics: Essays in Honor of Solomon Feferman, Lecture Notes in Logic 15, 444 pages, A K Peters, Ltd. ISBN 978-1-56881-169-7.
• Soare, Robert (1996). "Computability and Recursion". Bulletin of Symbolic Logic (2): 284–321.
• Syropoulos, Apostolos (2008). "Hypercomputation: Computing Beyond the Church–Turing Barrier". Springer. ISBN 978-0-387-30886-9.
• Turing, A. M. (1937) [Delivered to the Society November 1936], "On Computable Numbers, with an Application to the Entscheidungsproblem" (PDF), Proceedings of the London Mathematical Society, 2 42: 230–65, doidoi:10.1112/plms/s2-42.1.230 and Turing, A.M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. 2 43 (1937). стр. 544–6. doidoi:10.1112/plms/s2-43.6.544. (See also: Davis 1965:115ff)

Спољашње везе

• The Church–Turing Thesis entry by B. Jack Copeland in the Stanford Encyclopedia of Philosophy.
• Computation in Physical Systems —a comprehensive philosophical treatment of relevant issues
• Transcendental idealism and Post’s variant of the Church-Turing thesis —EGTheory blog