Дата на създаване на този документ: 31 март 2002, 21:04 ч.
Последна ревизия: 7 юли 2005, 3:46 ч.
Някъде през 1936-37 г., малко след появата на фундаменталната работа на Тюринг [Tur36], няколко различни изследователи, измежду които Алонзо Чърч, самият Алън Тюринг, и (според някои източници) също и Емил Пост, стигат независимо един от друг до заключението, че всички математически функции, мислими от човешкия ум, могат да бъдат пресмятани върху изчислително устройство, в наши дни известно като "Универсална Машина на Тюринг" (УMT)1.
Това знаменито твърдение е обикновено познато под името "Тезис на Чърч-Тюринг(-Пост)"; по-долу за краткост ние ще го отбелязваме само като "Ч-Т тезис".
Известни са различни еквиваленти формулировки на Ч-Т тезиса; онази, която ние ще използваме по-долу, е:
Дефиниция (Терзис на Чърч-Тюринг): Класът на всички интуитивно-изчислими математически функции съвпада с класа на функциите, изчислими върху УМТ.
Това твърдение с метафизична природа лежи сега в самитe основи на теоретичната компютърна наука, известна също като теоретична информатика, теория на aлгоритмите, или дискретна математика. Наистина, тезисът на Ч-Т е толкова широко приет в математическите и информатическите среди, че неговата валидност всъщност никога не е била сериозно поставяна под въпрос.2
Някъде около 1960 г. Едуард Фредкин предлага друга идея: че самата Вселена е някакво изчислително устройство, а именно, високо паралелна изчислителна машина, известна като "клетъчен автомат" (КА).
Предположението на Фредкин остава непубликувано до появата на играта "Живот" на Джон Конуей през 1969 г. и последвалите популярни публикации на Мартин Гарднър [Gar70, Gar71], посветени на тази игра и на клетъчните автомати като цяло. Именно Гарднър пръв анонсира идеята за "Вселената като клетъчен автомат" в негова публикация от февруари 1971 г., част от серия от статии в сп. "Scientific American", които по-късно са издадени в отделна книга [Gar83].
Първата публикация, специално посветена на Фредкин и неговата теория, обаче, се появява едва през 1988 г. под формата на интервю, дадено на Робърт Райт [Wri88a], което по-късно е разширено и излиза като част от книга [Wri88b].
И едва през 1990 г. самият Фредкин публикува статия [Fre90], посветена на тази тема, която се явява първата публикация на идеята в солидно научно списание.
Както често става в науката, обаче, оказва се, че Фредкин не е бил сам в тази посока от мисли... Хипотезата, че Вселената e може би клетъчен автомат, е била независимо предложена и публикувана от Конрад Цузе в края на шестдесетте години [Zus67, Zus69].
От гледна точка на модерната Теория на клетъчните автомати представите на Цузе са били до известна степен наивни. Все пак, докато Фредкин е бил първият, който е се е занимавал с изследване на тази теза до нейния пълен потенциал, приносът на Цузе, поне от историческа гледна точка, е еднакво важен. Ето защо, по-долу ние ще отдадем дължимото на тези двама мъже, като ги считаме и двамата за автори на тази наистина забележителна идея.
Предположението, направено от Цузе и Фредкин, сега се счита за основно твърдение в две относително нови научни области: Цифрова Механика (ЦМ) и Цифрова Физика (ЦФ).
В настоящата кратка статия ние няма да фокусираме нашето внимание върху разликите между тези две области, а по-скоро ще говорим за това кое е общото между тях.
И в цифровата механика, и в цифровата физика, ние смятаме твърдението, изказано от Цузе и Фредкин за вярно и ние оперираме с него точно както класическата компютърна наука оперира с тезиса на Чърч-Тюринг.
Ние наричаме това твърдение "Тезис на Цузе-Фредкин"; за краткост, по-долу ще го означаваме просто като "Ц-Ф тезис".
Дефиниция (Тезис на Цузе-Фредкин): Вселената е клетъчен автомат.
Макар да е претърпял повече от 40 години тихо развитие и да има значителна теория в негова подкрепа, тезисът на Ц-Ф си остава широко неизвестен и публично неприет.
В настоящата работа ние размишляваме относно взаимната "почти-еквивалентност" на Ч-Т и Ц-Ф тезисите, предлагайки това като силен аргумент в подкепа на последния.
Макар много аргументи в подкрепа на тезиса на Цузе-Фредкин да могат да бъдат изложени (вж. напр.: [Wri88a, Fre90]), следното, изглежда, се явява най-краткият аргумент, за който сме в състояние да си мислим.
Както ще покажем сега, ако ние се чувстваме уверени в истинността на тезиса на Чърч-Тюринг, няма причина да не се доверим също и на тезиса на Цузе-Фредкин; вярно е и обратното.
Нека първо да разгледаме обратното, а именно: че от тезиса на Ц-Ф непосредствено следва верността на класическия тезис на Ч-Т.
Aргументацията в подкрепа на това е доста директна:
Наистина, ако Вселената е универсален клетъчен автомат (УКА)3, всичко което се случва в този УКА е, очевидно, някакъв вид изчислителен процес, и тогава ние самите (заедно с нашите "математически мисли") не сме нищо повече от алгоритми, случващи се в някакво специфично място от пространство-времето на Автомата.
(Ако Вселената е клетъчен автомат, но нашите "интуитивно-изчислими математически функции" не(?) са алгоритми, то тогава моля кажете ни какво са те всъщност!)
От друга страна, всеки УКА може да емулира коя да е друга абстрактна изчислителна машина, включително УМТ4. Оттук следва и тезиса на Чърч-Тюринг.
Да започнем сега с тезиса на Чърч-Тюринг и да видим как той се явява eдно директно внушение в полза на тезиса на Цузе-Фредкин.
Преди всичко, нека да забележим, че Ч-Т тезисът е всъщност една "неразвита" форма на Ц-Ф тезиса; погледнато от някаква определена гледна точка, двете твърдения са всъщност повече или по-малко еквивалентни.
От една страна, Ч-Т тезисът твърди, че всяка интуитивно-изчислима математическа функция има своето изоморфно представяне (под формата на алгоритъм) върху едно (до известна степен примитивно) последователно изчислително устройство, а именно, УМТ.
Или, казано другояче:
Целият процес на човешко мислене е изоморфен (математически еквивалентен) на някакъв вид компютър.
Казано още по-кратко:
Всичко, за което сме в състояние да си мислим, е някакъв вид компютър.
От друга страна, тезисът на Ц-Ф твърди всъщност почти същото нещо: че самата Вселената е изчислително устройство, а именно, високо-паралелна машина, която ние наричаме КА.
Може да се каже също, че Ц-Ф тезисът е една директна "подсказка" (или даже: "физико-подобно следствие"), дадено ни от Ч-Т тезиса. Аргументацията за това е както следва:
Цялата физика – такава, каквато я познаваме – не е нищо друго освен опит да се "компресира" реалността във формули с цел да се построят "математически модели" (или "теории"), които обясняват феномените, извършващи се във Вселената.
Но, от друга страна, излиза, че всяка "формула" или "теория" може да бъде представена (според Ч-Т тезиса) върху УМТ.
Тъй като единствения начин, който ние познаваме, за да "изучаваме" (или "разбираме") реалността, е посредством математически модели/теории, то оттук до оригиналното твърдение на Цузе-Фредкин, че самата Вселената е някакъв вид изчислително устройство, а именно – клетъчен автомат, има само една крачка!
Оттук и предлаганата "почти-еквивалентност" на двата тезиса.
В съвременната теоретична физика съществува понятието за "Теория за всичко" (на англ.: "Theory of everything"). Последното е научен термин за означаване на една всеобхватна и вътрешно непротериворечива теория за всички процеси, извършващи се във Вселената, в която живеем.
Ако трябва да резюмираме съдържанието на настоящата статия, бихме могли да кажем следното:
През средата на тридесетте години на двадесети век Чърч и Тюринг достигат до идеята, че всяка теория, мислима от човешкия ум, може да бъде представена върху универсален компютър. (Тюринг, по-конкретно, предлага универсалната Машина на Тюринг (УМТ) като теоретичен изчислителен модел. Иначе, самата УМТ, която е последователно изчислително устройство, в никакъв случай не е най-добрият модел за извършване на изчисление; това е само един от многото, а по-точно – исторически първият абстрактен математически модел, за който е доказано, че е изчислително универсален)
През шестдесетте години Фредкин и Цузе предлагат друга идея: че "Теория за всичко", съществуващо във Вселената, може да бъде построена върху универсален компютър. (А следователно, самата Вселена, в която живеем – колкото и парадоксално това да изглежда на пръв поглед – също се явява някакъв вид компютър)
Фредкин и Цузе всъщност стигат и по-далеч: те изказват хипотезата, че решението на проблема за това какъв именно комютър се явява Вселената следва да бъде търсено в рамките на един сравнително по-тесен клас от математически модели за паралелно изчисление, известни като "клетъчни автомати".
Класическият тезис на Чърч-Тюринг е смятан за един успешен опит за математическа формализация на човешкото мислене и понятието "абстрактна математическа теория". В този смисъл бихме могли да кажем, че той има отношение към "вътрешния свят", т.е. към начина, по който човек възприема нещата чрез своя разум. По-късно, до голяма степен изненадващо, се оказва, обаче, че това метафизично твърдение има и друго, много по-мощно следствие, свързано с това какво представлява "външния свят", т.е. самата Вселена изобщо...
Предполагаме, че независимо от представения по-горе аргумент мнозина ще са склонни да отричат да признаят очевидната (според нас) силна връзка между двата тезиса. И тъй като Ч-Т тезисът е широко приет, докато тезисът на Ц-Ф не е, в областта на Цифровата Физика ние си служим и с двата тезиса: с първия – тезиса на Чърч-Тюринг – заради неговата добре установена, почти повсевместно призната валидност, и с втория – тезиса на Цузе-Фредкин – заради неговата специална формулировка, че Вселената е наистина именно КА (а не някакъв друг изчислителен модел).
Това е главно за да се избегнат всякакви продължителни и често тавталогични дискусии дали двете твърдения са наистина абсолютно еквивалентни, до каква степен те са еквивалентни (във връзка с въпроса "паралелизъм срещу последователност" на изчислителния модел), и неща от този род.
Настоящата статия се явява въвеждаща в една поредица от статии, посветени на Цифровата Физика [Pet02]. Ето защо, тук ние няма да се спираме на очевидния въпрос защо Вселената е все пак именно КА, а не някакъв друг изчислителен модел; именно този въпрос, обаче, ще бъде разгледан подробно в следващите статии от тази Серия [Pet02a2, Pet02a3].
* Тази статия е част от планирана поредица "Серия от кратки статии за Цифровата Физика" – вж. [Pet02].
1 "Универсална изчислителна машина" е терминът, използван от Тюринг за УМТ в [Tur36].
2 В модерните времена нещата малко се усложниха с предлагането на т.нар. "квантово изчисление" (КИ); надеждата тук е да се използват някои феномени, известни ни от квантовата механика, за да се демострират нови начини за извършване на изчисление. Обаче дори и защитниците на КИ всъщност не поставят под въпрос коректността на Ч-Т тезиса; те просто настояват, че някакъв вид "ускорение" ще бъде получено, ако използваме определени квантово-механични ефекти по време на изчислителния процес.
3 В своята оригинална форма тезисът на Цузе-Фредкин просто твърди, че Вселената е КА, не че е непременно УКА. Последното обаче често се смята за "мълчаливо загатнато" в дефиницията на Ц-Ф тезиса – по подобен начин ние сме свикнали напр. да си мислим за по-тесния, но по-мощен подклас на универсалните машини на Тюринг, когато говорим просто за "машини на Тюринг".
4 Докато самия факт, че дадена универсална изчислителна машина може да емулира коя да е друга (универсална) изчислителна машина е просто тавталогия, която следва от самата дефиниция на понятието за "изчислителна универсалност", подробното описание на самата емулация може понякога да бъде твърде сложно. За пример как играта "Живот" (която е двумерен универсален КА) може да емулира УМТ вж. [Ren00].
[Fre90] Fredkin, Edward, "Digital Mechanics: An Informational Process Based on Reversible Universal CA", Physica D 45 (1990) .
Онлайн версия: http://digitalphilosophy.org/dm_paper.htm
[Gar70] Gardner, Martin, "The Fantastic Combinations of John Conway's New Solitaire Game of 'Life' ", Scientific American 223 (October 1970) .
Онлайн версия: http://hensel.lifepatterns.net/october1970.html
[Gar71] Gardner, Martin, "Mathematical Games: On Cellular Automata, Self-Reproduction, the Garden of Eden, and the Game 'Life' ", Scientific American (February 1971) .
[Gar83] Gardner, Martin, "Wheels, Life and Other Mathematical Amusements", W.H.Freeman and Company (1983). Руски превод: "Крестики-нолики", Москва, Мир (1988). Вж. последните три глави от тази книга.
[Pet02] Petrov, Plamen, "Series of Brief Articles about Digital Physics (DP)", в процес на подготовка. За последна информация вж.: https://digitalphysics.org/Publications/Petrov/DPSeries/
[Pet02a2] Petrov, Plamen, "Church-Turing Thesis as an Immature Form of Zuse-Fredkin Thesis (More Arguments in Favour of the 'Universe as a Cellular Automaton' Idea)". Тази статия е част от [Pet02].
Онлайн версия: https://digitalphysics.org/Publications/Petrov/Pet02a2/Pet02a2.htm
[Pet02a3] Petrov, Plamen, "Zuse-Fredkin Thesis is the Ultimate Form of Church-Turing Thesis", в процес на подготовка. Тази статия е част от [Pet02].
[Ren00] Rendell, Paul, "A Turing Machine in Conway's Game of Life, extendable to a Universal Turing Machine", online document (02-Apr-2000). Публикувано в: Andrew Adamatzky (ed.), "Collision-Based Computing", Springer Verlag (2002). Вж. "Turing Universaility of the Game of Life".
Онлайн версия: http://rendell.server.org.uk/gol/tm.htm
[Tur36] Turing, Alan, "On Computable Numbers, With an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, Volume 42 (1936-37) ; Corrections, Ibid., vol. 43 (1937) . Препечатано в: M. David (ed.), "The Undecidable", Hewlett, NY: Raven Press (1965).
Онлайн версия: http://www.abelard.org/turpap2/tp2-ie.asp
[Wri88a] Wright, Robert, "Did the Universe Just Happen?", Atlantic Monthly (April 1988) 29-44. Български превод: "Компютър ли е Вселената?", Спектър 66 (1989) 42-51.
Онлайн версия (на английски език): https://digitalphysics.org/Publications/Wri88a/html/
Онлайн версия (на български език): https://digitalphysics.org/Publications/Wri88a-Bul/html/
[Wri88b] Wright, Robert, "Three Scientists and Their Gods: Looking for Meaning in an Age of Information", Times Books (1988). Вж. "Part One: Edward Fredkin".
[Zus67] Zuse, Konrad, "Rechnender Raum", Elektronische Datenverarbeitung 8 (1967) .
Електронна версия:
[Zus69] Zuse, Konrad, "Rechnender Raum", Schriften zur Datenverarbeitung, Band 1, Friedrich Vieweg & Sohn, Braunschweig (1969). Предвод на английски език: "Calculating Space", MIT Technical Translation AZT-70-164-GEMIT, MIT (Proj. MAC), Cambridge, Mass. 02139, Feb. 1970.
Електронна версия: