Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Машина Тьюринга на двухмерной сетке
Turing machine on a two dimensional grid
В информатике, турмит — это машина Тьюринга, которая, помимо текущего состояния, имеет ориентацию и "ленту", представляющую собой бесконечную двухмерную сетку ячеек. Также используются термины "ant" и "vant". Муравей Лэнгтона — хорошо известный тип турмита, определённый на ячейках квадратной сетки. Черви Патерсона — это тип турмита, определённый на рёбрах изометрической сетки. Было показано, что турмиты в целом эквивалентны по вычислительной мощности одномерным машинам Тьюринга с бесконечной лентой, поскольку каждый из них может имитировать работу другого.
In computer science, a turmite is a Turing machine which has an orientation in addition to a current state and a "tape" that consists of an infinite two dimensional grid of cells. The terms ant and vant are also used. Langton's ant is a well known type of turmite defined on the cells of a square grid. Paterson's worms are a type of turmite defined on the edges of an isometric grid. It has been shown that turmites in general are exactly equivalent in power to one dimensional Turing machines with an infinite tape, as either can simulate the other.
История
Муравьи Лэнгтона были изобретены в 1986 году и объявлены "эквивалентными машинам Тьюринга". Независимо от этого, в 1988 году Аллен Х. Брэди рассмотрел идею двухмерных машин Тьюринга с учетом ориентации и назвал их "TurNing-машинами". По-видимому, независимо от обоих этих исследователей, Грег Тёрк изучал ту же систему и написал об этом А. К. Дьюдни. А. К. Дьюдни назвал их "tur mites" в своей колонке "Компьютерные забавы" в журнале Scientific American в 1989 году. Руди Рукер рассказывает эту историю следующим образом:
Langton's ants were invented in 1986 and declared "equivalent to Turing machines". Independently, in 1988, Allen H. Brady considered the idea of two dimensional Turing machines with an orientation and called them "TurNing machines". Apparently independently of both of these, Greg Turk investigated the same kind of system and wrote to A. K. Dewdney about them. A. K. Dewdney named them "tur mites" in his "Computer Recreations" column in Scientific American in 1989. Rudy Rucker relates the story as follows:
цитата|Дьюдни сообщает, что, размышляя над названием для существ Тёрка, он подумал: "Что ж, это машины Тьюринга, изученные Тёрком, значит, в названии должно быть что-то от "Tur". И они похожи на маленьких насекомых или клещей, так что я назову их tur mites! А это звучит как "термиты!" С разрешения Тёрка и Дьюдни я уберу дефис и буду называть их турмитами.|Руди Рукер|Лаборатория искусственной жизни
quote|Dewdney reports that, casting about for a name for Turk's creatures, he thought, "Well, they're Turing machines studied by Turk, so they should be tur something. And they're like little insects, or mites, so I'll call them tur mites! And that sounds like termites!" With the kind permission of Turk and Dewdney, I'm going to leave out the hyphen, and call them turmites.|Rudy Rucker|Artificial Life Lab
Другие сетки
После первоначальной работы Аллена Х. Брэди с турмитами на треугольной сетке, также были исследованы шестиугольные покрытия. Большая часть этих работ принадлежит Тиму Хаттону, а его результаты доступны в Репозитории таблиц правил. Он также рассматривал турмитов в трех измерениях и собрал некоторые предварительные результаты. Аллен Х. Брэди и Тим Хаттон также исследовали одномерные относительные турмиты на целочисленной решетке, которые Брэди назвал флипперами. (Одномерные абсолютные турмиты, конечно, просто известны как машины Тьюринга.)
Following Allen H. Brady's initial work of turmites on a triangular grid, hexagonal tilings have also been explored. Much of this work is due to Tim Hutton, and his results are on the Rule Table Repository. He has also considered Turmites in three dimensions, and collected some preliminary results. Allen H. Brady and Tim Hutton have also investigated one dimensional relative turmites on the integer lattice, which Brady termed flippers. (One dimensional absolute turmites are of course simply known as Turing machines.)