Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Элементарлы жасушалық автомат
Elementary cellular automaton
110-қағидат жасушалық автомат (көбінесе жай ғана 110-қағидат деп аталады) – тұрақтылық пен хаос арасындағы шекарада қызықты мінез-құлық көрсететін элементарлы жасушалық автомат. Осы тұрғыдан алғанда, ол Конвейдің "Өмір ойынына" ұқсас. "Өмір" сияқты, 110-қағидаттың белгілі бір қайталама үлгісімен Тьюринг толықтығы дәлелденген. Бұл, теориялық тұрғыдан алғанда, кез келген есептеу немесе компьютерлік бағдарлама осы автоматты қолдану арқылы модельделуі мүмкін дегенді білдіреді.
The Rule 110 cellular automaton (often called simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 with a particular repeating background pattern is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
Тарих
2004 жылы Мэтью Кук 110-шы қағиданың белгілі бір қайталанатын фоны бар екенін және оның Тьюринг толықтығын, яғни 1985 жылы Стивен Вольфрам болжағандай, әмбебап есептеуге қабілетті екенін дәлелдеді. Кук өзінің дәлелін Вольфрамның "Жаңа ғылымның түрі" кітабы жарыққа шығар алдында Санта-Фе институтында өткен CA98 конференциясында таныстырды. Бұл Wolfram Research компаниясымен жасалған құпиялылық туралы келісімге байланысты сот ісіне әкелді. Wolfram Research компаниясы Кук дәлелінің жариялануын бірнеше жыл бойы кешіктірді.
In 2004, Matthew Cook published a proof that Rule 110 with a particular repeating background pattern is Turing complete, i. e., capable of universal computation, which Stephen Wolfram had conjectured in 1985. Cook presented his proof at the Santa Fe Institute conference CA98 before publication of Wolfram's book A New Kind of Science. This resulted in a legal affair based on a non disclosure agreement with Wolfram Research. Wolfram Research blocked publication of Cook's proof for several years.
Қызықты қасиеттері
88 мүмкін бірегей элементарлық жасушалық автоматтардың ішінде 110-қағида Тьюринг толықтығы тікелей дәлелденген жалғыз қағида, бірақ бірнеше ұқсас қағидалардың дәлелдемелері қарапайым салдарлар ретінде келеді (мысалы, 124-қағида, ол 110-қағиданың көлденең айналамы). 110-қағида, мүмкін, ең қарапайым белгілі Тьюринг толық жүйе. 110-қағида, «Өмір ойыны» сияқты, Вольфрам «4-сыныпты мінез-құлық» деп атаған нәрсені көрсетеді, ол толығымен тұрақты да емес, толығымен хаотикалық та емес. Жергілікті құрылымдар пайда болып, күрделі әрекеттеседі. Мэтью Кук 110-қағиданың циклдық тег жүйелерін, содан кейін 2 тег жүйесін, содан кейін Тьюринг машиналарын сәтті имитациялау арқылы әмбебап есептеуді қолдай алатынын дәлелдеді. Соңғы кезеңнің уақыт шығыны экспоненциалды, себебі Тьюринг машинасының таспасы бірлік сандық жүйемен кодталған. Нири мен Вудс (2006) 2 тег жүйесін сағат тілі бойынша Тьюринг машиналарымен алмастыратын және полиномдық үстеме шығынына ие болатын басқа құрылымды ұсынды.
Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been directly proven, although proofs for several similar rules follow as simple corollaries (e. g. Rule 124, which is the horizontal reflection of Rule 110). Rule 110 is arguably the simplest known Turing complete system. Rule 110, like the Game of Life, exhibits what Wolfram calls "Class 4 behavior", which is neither completely stable nor completely chaotic. Localized structures appear and interact in complex ways. Matthew Cook proved Rule 110 capable of supporting universal computation by successively emulating cyclic tag systems, then 2 tag system, and then Turing machines. The final stage has exponential time overhead because the Turing machine's tape is encoded with a unary numeral system. Neary and Woods (2006) presented a different construction that replaces 2 tag systems with clockwise Turing machines and has polynomial overhead.
Жалпыға ортақ дәліздеме
Мэтью Кук 110-қағиданың жалпыға бірдей екендігін дәлелдегенін "Жаңа ғылым түрі" басылымы жарық көрмей тұрып, Санта-Фе институтының конференциясында таныстырды. Wolfram Research бұл таныстырудың Куктың жұмыс берушімен жасасқан құпиялылық шартын бұзғанын мәлімдеді және Куктың мақаласын жарияланған конференция материалдарынан шығару үшін сотқа жүгінді. Дегенмен, Куктың дәлелінің бар екені белгілі болды. Оның дәлеліне қызығушылық оның нәтижесінен гөрі, әдістеріне, әсіресе оның құрылысының техникалық егжей-тегжейлеріне байланысты болды. Куктың дәлелінің мәні "Жаңа ғылым түрі" кітабындағы 110-қағида туралы талқылаудан едәуір өзгеше. Кук содан бері толық дәлелін баяндайтын мақала жазды. Кук 110-қағиданың әмбебап (немесе Тьюринг толық) екенін, оны басқа есептеу моделін – циклдық тег жүйесін эмуляциялауға болады, ал ол жүйе әмбебап екені белгілі деп дәлелдеді. Біріншіден, ол 110-қағида ғаламында шексіз қайталамалы үлгіде құруға болатын бірнеше ғарыш кемесін, өздігінен жалғасатын жергілікті үлгілерді анықтады. Содан кейін ол осы құрылымдардың комбинацияларын есептеу үшін пайдалануға болатын өзара әрекеттесу механизмін ойлап тапты.
Matthew Cook presented his proof of the universality of Rule 110 at a Santa Fe Institute conference, held before the publication of A New Kind of Science. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction. The character of Cook's proof differs considerably from the discussion of Rule 110 in A New Kind of Science. Cook has since written a paper setting out his complete proof. Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system, which is known to be universal. He first isolated a number of spaceships, self perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
110-баптағы ғарыш кемелерi
110-қағидада көрсетілген әмбебап машинаның жұмысы шекті сандағы локалданған үлгілерді шексіз қайталануға түсетін ая үлгісіне енгізуді қажет етеді. Ая үлгісі 14 ұяшықтан тұрады және әр жеті итерацияда дәлме-дәл қайталанады. Үлгі 00010011011111 болып табылады. 110-қағиданың әмбебап машинасы үшін үш локалданған үлгі ерекше маңызға ие. Олар төмендегі суретте ая үлгісімен қоршалған күйде көрсетілген. Сол жақтағы құрылым оңға қарай екі ұяшыққа жылғалысып, әр үш буын сайын қайталанады. Ол жоғарыда келтірілген ая үлгісімен қоршалған 0001110111 тізбегінен және осы тізбектің екі түрлі эволюциясынан тұрады. Суреттерде уақыт жоғарыдан төменге қарай өтеді: жоғарғы қатар бастапқы күйді, ал әрбір келесі қатар келесі уақыттағы күйді көрсетеді. Ортаңғы құрылым солға қарай сегіз ұяшыққа жылғалысып, әр отыз буын сайын қайталанады. Ол жоғарыда келтірілген ая үлгісімен қоршалған 1001111 тізбегінен және осы тізбектің жиырма тоғыз түрлі эволюциясынан тұрады. Оң жақтағы құрылым өз орнында қалып, жеті буын сайын қайталанады. Ол жоғарыда келтірілген ая үлгісімен қоршалған 111 тізбегінен және осы тізбектің бес түрлі эволюциясынан тұрады. Төменде бірінші екі құрылымның бір-бірімен тек аударма арқылы (сол жақта) өзара әрекеттеспей және үшінші құрылымды (оң жақта) құру үшін өзара әрекеттесетінін көрсететін сурет келтірілген. 110-қағидада көптеген басқа да «ғарыш кемелері» бар, бірақ олар әмбебаптық дәлелінде осылай көзге түспейді.
The function of the universal machine in Rule 110 requires a finite number of localized patterns to be embedded within an infinitely repeating background pattern. The background pattern is fourteen cells wide and repeats itself exactly every seven iterations. The pattern is 00010011011111. Three localized patterns are of particular importance in the Rule 110 universal machine. They are shown in the image below, surrounded by the repeating background pattern. The leftmost structure shifts to the right two cells and repeats every three generations. It comprises the sequence 0001110111 surrounded by the background pattern given above, as well as two different evolutions of this sequence. In the figures, time elapses from top to bottom: the top line represents the initial state, and each following line the state at the next time. The center structure shifts left eight cells and repeats every thirty generations. It comprises the sequence 1001111 surrounded by the background pattern given above, as well as twenty nine different evolutions of this sequence. The rightmost structure remains stationary and repeats every seven generations. It comprises the sequence 111 surrounded by the background pattern given above, as well as five different evolutions of this sequence. Below is an image showing the first two structures passing through each other without interacting other than by translation (left), and interacting to form the third structure (right). There are numerous other spaceships in Rule 110, but they do not feature as prominently in the universality proof.
Циклдік белгілеу жүйесі жұмыс істейді
Жоғарыдағы сурет 110-шы ереже бойынша циклдік таңба жүйесін қайта құрудың схемалық диаграммасы.
The figure above is the schematic diagram of the reconstruction of a cyclic tag system in Rule 110.