Есептеу мүмкіндігінің табиғаты: Чёрч-Тьюринг тезисі

Кіріспе

Есептеуге қабілеттіліктің табиғаты туралы тезис

Есептеуге қабілеттілік теориясында Черч-Тьюринг тезисі (сондай-ақ есептеуге қабілеттілік тезисі, Тьюринг-Черч тезисі, Черч-Тьюринг болжамы, Черч тезисі, Черч болжамы және Тьюринг тезисі деп те аталады) – есептеуге қабілетті функциялардың табиғаты туралы тезис. Ол табиғи сандардағы функция тиімді әдіспен есептелуі мүмкін, егер және тек егер ол Тьюринг машинасымен есептелетін болса дейді. Тезис американдық математик Алонзо Черч пен британдық математик Алан Тьюрингтің есімімен аталады. Есептелетін функцияның нақты анықтамасынан бұрын математиктер қағаз және қарындаш әдістерімен есептелетін функцияларды сипаттау үшін «тиімді есептелетін» деген бейресми терминді жиі қолданды. 1930 жылдары есептеуге қабілеттілік туралы түсінікті ресмилендіруге бірнеше тәуелсіз әрекеттер жасалды:

1933 жылы Курт Гёдель, Жак Гербрандпен бірге, жалпы рекурсивті функциялардың сыныбының анықтамасын ресмилендірді: функциялардың ең кіші сыныбы (көптеген аргументтері бар), ол композиция, рекурсия және минимизация бойынша жабық, және нөлді, ізбасарды және барлық проекцияларды қамтиды. 1936 жылы Алонзо Черч функцияларды анықтау үшін λ-саны деп аталатын әдіс жасады. λ-калькулі ішінде ол Чирк сандары деп аталатын табиғи сандардың кодталуын анықтады. Натурал сандардағы функция λ-есептеуге болатын деп аталады, егер шіркеу сандарының сәйкес функциясы λ-калькулісінің бір термінімен бейнеленсе. Сондай-ақ, 1936 жылы, Черчтың жұмысын білмей тұрып, Алан Тьюринг машиналар үшін теориялық модель жасады, қазір Тьюринг машиналары деп аталады, олар таспадағы символдарды манипуляциялау арқылы кіріспен есептеулерді жүргізе алады. Табиғи сандарды символдар тізбегі ретінде кодтауды ескере отырып, егер кейбір Тьюринг машинасы кодталған табиғи сандардағы сәйкес функцияны есептеп шығарса, онда табиғи сандардағы функция Тьюрингтік есептелетін деп аталады. Черч, Клин және Тьюринг осы үш формальды түрде анықталған есептелетін функциялардың кластары сәйкес келетінін дәлелдеді: функция λ-есептелетін болса және тек Тьюринг есептелетін болса ғана, және егер ол жалпы рекурсивті болса ғана. Бұл математиктер мен компьютерлік ғалымдарды есептеуге қабілеттілік туралы түсінік осы үш тең процесспен сипатталады деп сенуге итермеледі. Есептеуге қабілеттілікті сипаттаудың басқа да ресми әрекеттері кейіннен осы сенімді нығайтты (төменде қараңыз). Екінші жағынан, Черч-Тьюринг тезисі жоғарыда аталған формальды түрде анықталған үш есептелетін функция класы «тиімді есептелетін» функция туралы бейресми түсінікпен сәйкес келеді деп мәлімдейді. Теорияның кеңінен қабылдануына қарамастан, оны ресми түрде дәлелдеу мүмкін емес, өйткені «тиімді есептеу» ұғымы тек бейресми түрде анықталған. Оның пайда болуынан бастап, бастапқы тезистің түрленулері пайда болды, соның ішінде біздің ғаламдағы компьютермен физикалық түрде не жүзеге асырылуы мүмкін екендігі туралы мәлімдемелер (физикалық Черч-Тьюринг тезисі) және тиімді есептелуі (Черч-Тьюринг тезисі (кешенділік теориясы)). Бұл өзгерістер Черч пен Тьюрингке байланысты емес, кешенділік теориясы мен цифрлық физикадағы кейінгі жұмыстардан туындайды. Бұл тезис сонымен қатар ақыл-ой философиясына да әсер етеді (төменде қараңыз).

In 1933, Kurt Gödel, with Jacques Herbrand, formalized the definition of the class of general recursive functions: the smallest class of functions (with arbitrarily many arguments) that is closed under composition, recursion, and minimization, and includes zero, successor, and all projections. In 1936, Alonzo Church created a method for defining functions called the λ calculus. Within λ calculus, he defined an encoding of the natural numbers called the Church numerals. A function on the natural numbers is called λ computable if the corresponding function on the Church numerals can be represented by a term of the λ calculus. Also in 1936, before learning of Church's work, Alan Turing created a theoretical model for machines, now called Turing machines, that could carry out calculations from inputs by manipulating symbols on a tape. Given a suitable encoding of the natural numbers as sequences of symbols, a function on the natural numbers is called Turing computable if some Turing machine computes the corresponding function on encoded natural numbers. Church, Kleene, and Turing proved that these three formally defined classes of computable functions coincide: a function is λ computable if and only if it is Turing computable, and if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes. Other formal attempts to characterize computability have subsequently strengthened this belief (see below). On the other hand, the Church–Turing thesis states that the above three formally defined classes of computable functions coincide with the informal notion of an effectively calculable function. Although the thesis has near universal acceptance, it cannot be formally proven, as the concept of effective calculability is only informally defined. Since its inception, variations on the original thesis have arisen, including statements about what can physically be realized by a computer in our universe (physical Church Turing thesis) and what can be efficiently computed (Church–Turing thesis (complexity theory)). These variations are not due to Church or Turing, but arise from later work in complexity theory and digital physics. The thesis also has implications for the philosophy of mind (see below).

Кейінгі дамуы

"Нәтижелі есептеу" ұғымын жақсырақ түсінуге тырысу 1980 жылы Робин Гандиді (Тьюрингтің шәкірті және досы) машиналық есептеуді талдауға (Тьюринг машинасы арқылы іске асырылатын адам есептеуінен өзгеше) бастады. Гандидің жасушалық автоматтарға (Конвейдің өмір ойыны сияқты), параллелизмге және кристалл автоматтарға деген қызығушылығы мен талдауы оны төрт "принципті (немесе шектеуді) ұсынуға әкелді, оларды кез келген машина қанағаттандыруы тиіс деп саналады". Оның ең маңызды төртінші принципі – "себеп-салдар принципі" "әсерлер мен сигналдардың таралуының шекті жылдамдығына" негізделген; қазіргі физика қашықтықтан бірден әрекет ету мүмкіндігін жоққа шығарады. Осы принциптер мен қосымша шектеулер негізінде – (1а) кез келген бөліктің сызықтық өлшемдерінің ең төменгі шегі, (1б) таралу жылдамдығының (жарық жылдамдығы) ең жоғарғы шегі, (2) машинаның дискретті дамуы және (3) детерминистік мінез-құлқы – «I–IV принциптерін қанағаттандыратын құрылғымен есептелетін нәрсе есептеуге болады» деген теорема туындайды. 1990 жылдардың соңында Вильфрид Зиг Тьюринг пен Гандидің «тиімді есептеу» тұжырымдарын «бейресми ұғымды нақтылау, оның жалпы ерекшеліктерін аксиомалық түрде қалыптастыру және аксиомалық базаны зерттеу» мақсатымен талдады. 1997 және 2002 жылдарғы жұмыстарында Зиг «механикалық түрде жұмыс істейтін адам есептеуші агент» – компьютердің мінез-құлқына қатысты бірқатар шектеулерді ұсынады. Бұл шектеулер мыналар:
"(B.1) (Шектелу) Компьютер бірден тани алатын символдық конфигурациялардың санына белгілі бір шектеу бар."
"(B.2) (Шектелу) Компьютерде бола алатын ішкі күйлердің санына нақты шектеу бар."
"(L.1) (Жергіліктілік) Компьютер тек байқалатын символдық конфигурацияның элементтерін ғана өзгерте алады."
"(L.2) (Жергіліктілік) Компьютер бір символдық конфигурациядан екіншісіне көңіл аударуы мүмкін, бірақ жаңа байқалған конфигурациялар бірден бұрын байқалған конфигурациядан белгілі бір қашықтықта болуы керек."
"(D) (Детерминизм) Бірден танылатын (ішкі) конфигурация келесі есептеу қадамын (және сәттегі сипаттаманы) бірегей түрде анықтайды"; басқаша айтқанда: "Компьютердің ішкі күйі байқалатын конфигурациямен бірге келесі есептеу қадамын және келесі ішкі күйді бірегей түрде анықтайды." Бұл мәселе академиялық қауымдастықта белсенді талқыланып жатыр.

An attempt to understand the notion of "effective computability" better led Robin Gandy (Turing's student and friend) in 1980 to analyze machine computation (as opposed to human computation acted out by a Turing machine). Gandy's curiosity about, and analysis of, cellular automata (including Conway's game of life), parallelism, and crystalline automata, led him to propose four "principles (or constraints) which it is argued, any machine must satisfy". His most important fourth, "the principle of causality" is based on the "finite velocity of propagation of effects and signals; contemporary physics rejects the possibility of instantaneous action at a distance". From these principles and some additional constraints—(1a) a lower bound on the linear dimensions of any of the parts, (1b) an upper bound on speed of propagation (the velocity of light), (2) discrete progress of the machine, and (3) deterministic behavior—he produces a theorem that "What can be calculated by a device satisfying principles I–IV is computable." In the late 1990s Wilfried Sieg analyzed Turing's and Gandy's notions of "effective calculability" with the intent of "sharpening the informal notion, formulating its general features axiomatically, and investigating the axiomatic framework". In his 1997 and 2002 work Sieg presents a series of constraints on the behavior of a computor—"a human computing agent who proceeds mechanically". These constraints reduce to:
"(B.1) (Boundedness) There is a fixed bound on the number of symbolic configurations a computor can immediately recognize. "(B.2) (Boundedness) There is a fixed bound on the number of internal states a computor can be in. "(L.1) (Locality) A computor can change only elements of an observed symbolic configuration. "(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration. "(D) (Determinacy) The immediately recognizable (sub )configuration determines uniquely the next computation step (and id [instantaneous description])"; stated another way: "A computor's internal state together with the observed configuration fixes uniquely the next computation step and the next internal state." The matter remains in active discussion within the academic community.

Анықтама ретінде диссертация

Дипломдық жұмысты қарапайым математикалық анықтама ретінде қарастыруға болады. Гедельдің осы тақырыптағы пікірлері осы көзқарасқа нұсқайды, мысалы, "механикалық есептеудің дұрыс анықтамасын Тьюринг кез келген күмәнсіз орнатып берді". Роберт И. Соар бұл тезистің тек анықтама екенін нақты айтады, сондай-ақ Тьюрингтің есептеу қабілеттілігінің анықтамасы үздіксіз функцияның эпсилон-дельта анықтамасымен бірдей дәрежеде дұрыс болуы мүмкін екенін дәлелдейді.

Диссертацияның сәттілігі

Нақты есептеуді / есептеуді сипаттау үшін рекурсия, λ-есеп және Тьюринг машинасынан басқа да формализмдер ұсынылған. Клейн (1952) тізімге Курт Гёдельдің 1936 жылғы «S1 жүйесінде есептелетін» функцияларын және Эмиль Посттың (1943, 1946) «каноникалық [немесе нормалды] жүйелерін» қосады. 1950 жылдары Хао Ванг пен Мартин Дэвис бір таспалы Тьюринг машинасының моделін (Post–Turing машинасы) едәуір жеңілдетті. Марвин Мински модельді екі немесе одан көп таспаға кеңейтті және таспаларды «жоғары-төмен қозғалатын санау машиналарына» қарапайымдастырды, оны Мелзак пен Ламбек одан әрі дамытып, қазіргі «сақтау машинасы» моделі деп таныстырды. 1960 жылдардың соңы мен 1970 жылдардың басында зерттеушілер сақтау машинасының моделін компьютердің қазіргі заманғы түсінігіне жақын «тіркегіш машинасына» кеңейтті. Басқа модельдерге комбинаторлық логика және Марков алгоритмдері жатады. Гуревич Колмогоров пен Успенскийдің (1953, 1958) «көрсеткіш машинасы» моделін қосады: «Олар тек өзіне-өзі есептеу функциясының түсінігін кеңейтудің жолы жоқ екеніне көз жеткізгісі келді». Бұл үлкен еңбектердің барлығы модельдердің Тьюринг машинасына есептеу жағынан балама екендігін дәлелдейді; мұндай модельдер Тьюринг толық деп аталады. «Нақты есептеу / есептеу» ұғымын формалдауға жасалған барлық осы әрекеттер бірдей нәтижелер бергендіктен, қазіргі кезде Чёрч-Тьюринг тезисі дұрыс деп есептеледі. Шындығында, Гёдель (1936) осыдан да күштірек бір нәрсені ұсынды; ол «S1 жүйесінде есептеуге болатын» ұғымның «абсолютті» екенін байқады:

Вариациялар

Черч-Тьюринг тезисінің сәттілігі тезистің түрленулерін ұсынуға ықпал етті. Мысалы, физикалық Черч-Тьюринг тезисі былай глайды: «Барлық физикалық есептелетін функциялар – Тьюринг есептелетін функциялар». Черч-Тьюринг тезисі есептеудің бір моделі екіншісін қаншалықты тиімді түрде симуляциялай алатыны туралы ештеңе айтпайды. Мысалы, (көп ленталы) әмбебап Тьюринг машинасы кез келген Тьюринг машинасының симуляциясында тек логарифмдік баяулауға ұшырайды. Черч-Тьюринг тезисінің бір түрі кездейсоқ, бірақ «ақылға қонымды» есептеу моделін тиімді түрде симуляциялау мүмкіндігін қарастырады. Бұл мүмкіншілік тезисі деп аталады, сондай-ақ (классикалық) күрделілік теориясы Черч-Тьюринг тезисі немесе кеңейтілген Черч-Тьюринг тезисі деп те аталады, ол Черч немесе Тьюрингке емес, күрделілік теориясының дамуында біртіндеп қалыптасқан. Онда: «Ықтималдық Тьюринг машинасы кез келген нақты есептеу моделін тиімді түрде симуляциялай алады» делінген. Мұндағы «тиімді» сөзі полиномиалдық уақыт азайтуды білдіреді. Бұл тезис бастапқыда Этан Бернштейн мен Умеш Вазирани (1997) еңбектерінде «есептеу күрделілігі теориясы Черч-Тьюринг тезисі» деп аталды. Осылайша, күрделілік теориясы Черч-Тьюринг тезисі есептеудің барлық «ақылға қонымды» модельдері полиномиалдық уақытта есептелетін проблемалардың бірдей класын береді деп болжайды. Егер ықтималдық полиномиалдық уақыт (BPP) детерминистік полиномиалдық уақытқа (P) тең болса, «ықтималдық» сөзі күрделілік теориясы Черч-Тьюринг тезисінде қажет емес. Осыған ұқсас тезисті инварианттық тезис деп атаған Сес Ф. Слот пен Питер ван Эмде Боас енгізді. Онда былай делінген: «Ақылға қонымды» машиналар бір-бірін полиномиалдық шектеулі уақыт және кеңістіктегі тұрақты факторлар арасында симуляциялай алады». Тезис алғаш рет STOC'84 конференциясындағы мақалада пайда болды, онда Тьюринг машинасының симуляциясында полиномиалдық уақыт пен тұрақты кеңістік бірдей қол жеткізілуі мүмкін екені көрсетілді. Егер BQP, BPP-нің нақты үстін жиыны болып шықса, бұл күрделілік теориясы Черч-Тьюринг тезисін жоққа шығарады. Яғни, тиімді ықтималдық алгоритмдері жоқ тапсырмаларды орындайтын тиімді кванттық алгоритмдер болады. Бұл бастапқы Черч-Тьюринг тезисін жоққа шығармайды, себебі кванттық компьютерді әрқашан Тьюринг машинасы симуляциялай алады, бірақ тиімділік тұрғысынан классикалық күрделілік теориясы Черч-Тьюринг тезисін жоққа шығарады. Осыған байланысты кванттық күрделілік теориясы Черч-Тьюринг тезисі былай глайды: Олар тезиспен қамтылмаған есептеу формаларының бүгінде маңызды екенін, оларды «супер Тьюринг есептеулері» деп атайды.

The success of the Church–Turing thesis prompted variations of the thesis to be proposed. For example, the physical Church–Turing thesis states: "All physically computable functions are Turing computable." The Church–Turing thesis says nothing about the efficiency with which one model of computation can simulate another. It has been proved for instance that a (multi tape) universal Turing machine only suffers a logarithmic slowdown factor in simulating any Turing machine. A variation of the Church–Turing thesis addresses whether an arbitrary but "reasonable" model of computation can be efficiently simulated. This is called the feasibility thesis, also known as the (classical) complexity theoretic Church–Turing thesis or the extended Church–Turing thesis, which is not due to Church or Turing, but rather was realized gradually in the development of complexity theory. It states: "A probabilistic Turing machine can efficiently simulate any realistic model of computation." The word 'efficiently' here means up to polynomial time reductions. This thesis was originally called computational complexity theoretic Church–Turing thesis by Ethan Bernstein and Umesh Vazirani (1997). The complexity theoretic Church–Turing thesis, then, posits that all 'reasonable' models of computation yield the same class of problems that can be computed in polynomial time. Assuming the conjecture that probabilistic polynomial time (BPP) equals deterministic polynomial time (P), the word 'probabilistic' is optional in the complexity theoretic Church–Turing thesis. A similar thesis, called the invariance thesis, was introduced by Cees F. Slot and Peter van Emde Boas. It states: Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant factor overhead in space." The thesis originally appeared in a paper at STOC'84, which was the first paper to show that polynomial time overhead and constant space overhead could be simultaneously achieved for a simulation of a Random Access Machine on a Turing machine. If BQP is shown to be a strict superset of BPP, it would invalidate the complexity theoretic Church–Turing thesis. In other words, there would be efficient quantum algorithms that perform tasks that do not have efficient probabilistic algorithms. This would not however invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical complexity theoretic Church–Turing thesis for efficiency reasons. Consequently, the quantum complexity theoretic Church–Turing thesis states: They claim that forms of computation not captured by the thesis are relevant today,
terms which they call super Turing computation.

Философиялық әсерлері

Философтар Черч-Тюринг тезисін сана философиясымен байланыстырып қарастырды. Б. Джек Коупленд ұзақ мерзімді перспективада Тьюринг машинасымен модельдеуге келмейтін нақты детерминистік физикалық процестердің болуы ашық эмпирикалық сұрақ екенін айтады; сондай-ақ, ол мұндай процестердің адам миының жұмысына қатысы бар-жоғы да ашық эмпирикалық сұрақ екенін көрсетеді. Черч-Тюринг тезисі мен физика арасындағы қарым-қатынас, сондай-ақ гиперкомпьютерлік есептеу мүмкіндігін қамтитын бірқатар маңызды ашық мәселелер де бар. Физика саласында қолданғанда, тезистің бірнеше түсіндірілуі мүмкін:

Ғалам Тьюринг машинасына баламалы; демек, рекурсивті емес функцияларды есептеу физикалық жағынан мүмкін емес. Бұл күшті Черч-Тюринг тезисі немесе Черч-Тюринг-Дойч принципі деп аталады және ол цифрлық физиканың негізін құрайды. Ғалам Тьюринг машинасына баламалы емес (яғни, физика заңдары Тьюрингтік есептеуге келмейді), бірақ есептеуге келмейтін физикалық құбылыстар гиперкомпьютер құру үшін "пайдаланылмайды". Мысалы, физикасында есептеуге болатын нақты сандардың орнына кездейсоқ нақты сандар бар ғалам осы санатқа жатады. Ғалам – гиперкомпьютер, және осы қасиетті пайдаланып, рекурсивті емес функцияларды есептеуге қабілетті физикалық құрылғылар жасау мүмкін. Мысалы, барлық кванттық-механикалық құбылыстар Тьюрингтік есептеуге келмеуі мүмкін, бірақ кванттық Тьюринг машиналары сияқты қатаң модельдер детерминистік Тьюринг машиналарына тең екені белгілі. (Олар міндетті түрде тиімді тең емес; жоғарыда қараңыз.) Джон Лукас және Роджер Пенроуз адам санасының кванттық механикалық түрде күшейтілген, "алгоритмдік емес" есептеудің нәтижесі болуы мүмкін деген пікірді білдірді. Осы үш санатқа кірмейтін немесе олардың арасында жатқан көптеген техникалық мүмкіндіктер бар, бірақ олар концепцияның кеңдігін көрсетуге көмектеседі. Тезистің философиялық аспектілері, физикалық және биологиялық компьютерлерге қатысты, сондай-ақ Одифреддидің 1989 жылғы рекурсия теориясы бойынша оқулығында талқыланады.

Есептелмейтін функциялар

Есептеуге болмайтын функцияларды формалды түрде анықтауға болады. Мұндай функциялардың кеңінен танымал мысалы – "Құдалы бобр" функциясы. Бұл функция n енгізілімін қабылдайды және кіріссіз іске қосылғанда, n күйі бар Тьюринг машинасы тоқтағанға дейін басып шығаратын символдардың ең көп санын қайтарады. Құдалы бобр функциясының жоғарғы шегін табу – тоқтау мәселесін шешумен тең, және бұл мәселенің Тьюринг машиналарымен шешілмейтіні белгілі. Құдалы бобр функциясын Тьюринг машиналары есептей алмайтындықтан, Черч-Тьюринг тезисі бұл функцияны ешқандай әдіспен тиімді есептеуге болмайды деп мәлімдейді. Бірнеше есептеу модельдері (Черч-Тьюринг) есептеуге болмайтын функцияларды есептеуге мүмкіндік береді. Бұлар гиперкомпьютерлер деп аталады. Марк Бергин индуктивті Тьюринг машиналары сияқты суперрекурсивті алгоритмдер Черч-Тьюринг тезисін жоққа шығарады деп санайды. Оның аргументі алгоритмнің дәстүрлі анықтамасынан кеңірек анықтамаға негізделген, сондықтан кейбір индуктивті Тьюринг машиналарынан алынған есептеуге келмейтін функциялар есептелуге болады. Черч-Тьюринг тезисінің бұл түсіндірмесі жоғарыда талқыланған есептеу теориясындағы қалыптанған түсіндірмеден өзгеше. Суперрекурсивті алгоритмдердің шын мәнінде Черч-Тьюринг тезисінің мағынасындағы алгоритмдер екендігі туралы пікір есептеуді зерттеу қауымдастығында кең қолдау таппады.