Turmite (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, une turmite est une machine de Turing bi-dimensionnelle dont la « bande » consiste en une grille infinie dont chaque case (ou dans certains cas chaque nœud ou arête) peut être écrite ou effacée par une « tête » dont l'orientation change à chaque itération en fonction de l'état de la cellule où elle est située. Le terme « turmite » fait référence en anglais à la fois à « Turing machine » (« machine de Turing ») et à « termite ». Une telle machine est également appelée « fourmi » lorsqu'elle utilise une grille de cases carrées (comme dans le cas de la fourmi de Langton) et une « abeille » ou un « ver » dans le cas d'une grille hexagonale (comme les vers de Paterson). (fr) En ciencias de la computación, un Turmite es una Máquina de Turing que se vale de una cinta bidimensional, haciendo alusión a la Teoría de la computabilidad, un Turmite tiene el mismo poder que una Máquina de Turing determinista; por el hecho que acepta y decide el mismo tipo de lenguajes (enumerables recursivamente y recursivos, respectivamente) y computa exactamente las mismas funciones totales y parciales (las recursivas minimizadas limitadas y las recursivas minimizadas ilimitadas, respectivamente), empero, en la teoría de la Complejidad computacional, un Turmite con cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con cintas (siendo el número mínimo con el cual se logre la máxima eficacia), o sea, aproximadamente en tiempo , siendo el tiempo en el que ese mismo problema es resuelto por una MT determinista de una sola cinta. (es) 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. (en) Em ciência da computação, uma turmite é uma Máquina de Turing que tem uma orientação, bem como um estado atual e uma fita que consiste de uma grade bidimensional infinita de células. Os termos ant(inglês) , formiga(português) e vant também são usados. Formiga de Langton é um tipo bem conhecido de turmite definida sobre as células de uma grade quadrada. Paterson's worms é um tipo de turmite definida nos limites de uma grade isométrica. Tem sido demonstrado que turmites em geral, são exatamente equivalentes em poder a máquinas unidimensionais Turing com uma fita infinita, pois uma pode simular a outra. (pt) Turmit – dwuwymiarowy model obliczeń będący połączeniem maszyny Turinga i modelu Langtona. Wykazano, że odpowiadają pod względem możliwości obliczeniowych jednowymiarowej maszynie Turinga. W przeciwieństwie do jednowymiarowych maszyn Turinga taśma zawiera się siatce komórek, które mogą zostać zmodyfikowane przez aktywny element (czoło). Zmienia on swój kierunek poruszania w każdej iteracji w zależności od swojego własnego stanu i stanu komórki, na jakiej się znajduje. "Czoło" struktury nazywane jest zwykle mrówką lub turmitem (od termit i Turing) dla siatek kwadratowych oraz pszczołą, robakiem lub żółwiem dla siatek heksagonalnych (sześciokątnych). Pojedynczy turmit określany jest przez zmienne jego pozycji, kierunku i stanu. (pl) В інформатиці Тюрміт — машина Тюрінга, яка має орієнтацію в просторі, поточний стан і «стрічку», що складається з нескінченного двомірного масиву комірок. Прикладами тюрмітів можуть слугувати мураха Ленгтона, визначений на комірках квадратної сітки і черв'яки Патерсона, визначений на ребрах трикутної сітки. Тюрміти за своєю обчислювальною здатністю еквівалентні звичайній одновимірній машині Тюрінга. (uk) В информатике Тьюрмит — это машина Тьюринга, которая имеет ориентацию в пространстве, текущее состояние и «ленту», состоящую из бесконечного двухмерного массива ячеек. Примерами тьюрмитов могут служить муравей Лэнгтона, определённый на ячейках квадратной сетки, и черви Патерсона, определённые на рёбрах треугольной сетки. Тьюрмиты по своей вычислительной способности эквивалентны обычной одномерной машине Тьюринга. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Turmite-120121010011-8342.png?width=300 |
| dbo:wikiPageExternalLink | http://digbybare.com/turmite http://mathworld.wolfram.com/Turmite.html https://gollygang.github.io/ruletablerepository/downloads/Turmites.zip http://www.maa.org/editorial/mathgames/mathgames_06_07_04.html http://www.maa.org/editorial/mathgames/mathgames_10_24_03.html%7Ctitle=Math https://github.com/GollyGang/ruletablerepository/wiki/TwoDimensionalTuringMachines https://web.archive.org/web/20040323220627/http:/www.maa.org/editorial/mathgames/mathgames_10_24_03.html https://web.archive.org/web/20130516052344/http:/www.maa.org/editorial/mathgames/mathgames_06_07_04.html https://web.archive.org/web/20131221162630/http:/digbybare.com/turmite |
| dbo:wikiPageID | 1694744 (xsd:integer) |
| dbo:wikiPageLength | 10081 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1085641658 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rudy_Rucker dbr:Scientific_American dbr:Paterson's_worms dbr:Integer_lattice dbr:MathWorld dbc:Turing_machine dbr:State_transition_table dbr:Computer_science dbr:A._K._Dewdney dbr:Busy_Beaver dbc:Artificial_life dbr:Triangular_tiling dbr:U-turn dbr:Langton's_ant dbc:Cellular_automaton_rules dbr:Fractal dbr:Isotropic dbc:Models_of_computation dbr:Hexagonal_tiling dbr:Greg_Turk dbr:Ed_Pegg,_Jr. dbr:Turing_machine dbr:Square_tiling dbr:Langton's_Ant dbr:Fibonacci_spiral dbr:File:Turmite-120121010011-8342.png |
| dbp:wikiPageUsesTemplate | dbt:Annotated_link dbt:Cite_web dbt:Commons_category dbt:Distinguish dbt:Quote dbt:Short_description |
| dcterms:subject | dbc:Turing_machine dbc:Artificial_life dbc:Cellular_automaton_rules dbc:Models_of_computation |
| gold:hypernym | dbr:Machine |
| rdf:type | owl:Thing dbo:Software yago:WikicatCellularAutomata yago:WikicatModelsOfComputation yago:Anomaly109606527 yago:Assistant109815790 yago:Automaton109825519 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | 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. (en) В інформатиці Тюрміт — машина Тюрінга, яка має орієнтацію в просторі, поточний стан і «стрічку», що складається з нескінченного двомірного масиву комірок. Прикладами тюрмітів можуть слугувати мураха Ленгтона, визначений на комірках квадратної сітки і черв'яки Патерсона, визначений на ребрах трикутної сітки. Тюрміти за своєю обчислювальною здатністю еквівалентні звичайній одновимірній машині Тюрінга. (uk) В информатике Тьюрмит — это машина Тьюринга, которая имеет ориентацию в пространстве, текущее состояние и «ленту», состоящую из бесконечного двухмерного массива ячеек. Примерами тьюрмитов могут служить муравей Лэнгтона, определённый на ячейках квадратной сетки, и черви Патерсона, определённые на рёбрах треугольной сетки. Тьюрмиты по своей вычислительной способности эквивалентны обычной одномерной машине Тьюринга. (ru) En ciencias de la computación, un Turmite es una Máquina de Turing que se vale de una cinta bidimensional, haciendo alusión a la Teoría de la computabilidad, un Turmite tiene el mismo poder que una Máquina de Turing determinista; por el hecho que acepta y decide el mismo tipo de lenguajes (enumerables recursivamente y recursivos, respectivamente) y computa exactamente las mismas funciones totales y parciales (las recursivas minimizadas limitadas y las recursivas minimizadas ilimitadas, respectivamente), empero, en la teoría de la Complejidad computacional, un Turmite con cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con cintas (siendo el número mínimo con el cual se logre la máxima eficacia), o sea, aproximadamente en tiempo , siendo el tiempo en el (es) En informatique théorique, une turmite est une machine de Turing bi-dimensionnelle dont la « bande » consiste en une grille infinie dont chaque case (ou dans certains cas chaque nœud ou arête) peut être écrite ou effacée par une « tête » dont l'orientation change à chaque itération en fonction de l'état de la cellule où elle est située. (fr) Em ciência da computação, uma turmite é uma Máquina de Turing que tem uma orientação, bem como um estado atual e uma fita que consiste de uma grade bidimensional infinita de células. Os termos ant(inglês) , formiga(português) e vant também são usados. Formiga de Langton é um tipo bem conhecido de turmite definida sobre as células de uma grade quadrada. Paterson's worms é um tipo de turmite definida nos limites de uma grade isométrica. (pt) Turmit – dwuwymiarowy model obliczeń będący połączeniem maszyny Turinga i modelu Langtona. Wykazano, że odpowiadają pod względem możliwości obliczeniowych jednowymiarowej maszynie Turinga. W przeciwieństwie do jednowymiarowych maszyn Turinga taśma zawiera się siatce komórek, które mogą zostać zmodyfikowane przez aktywny element (czoło). Zmienia on swój kierunek poruszania w każdej iteracji w zależności od swojego własnego stanu i stanu komórki, na jakiej się znajduje. Pojedynczy turmit określany jest przez zmienne jego pozycji, kierunku i stanu. (pl) |
| rdfs:label | Turmite (es) Turmite (fr) Turmit (pl) Тьюрмиты (ru) Turmite (en) Turmite (pt) Тюрміти (uk) |
| owl:differentFrom | dbr:Termite |
| owl:sameAs | freebase:Turmite yago-res:Turmite wikidata:Turmite dbpedia-es:Turmite dbpedia-fr:Turmite dbpedia-he:Turmite dbpedia-pl:Turmite dbpedia-pt:Turmite dbpedia-ru:Turmite dbpedia-uk:Turmite https://global.dbpedia.org/id/2sma7 |
| prov:wasDerivedFrom | wikipedia-en:Turmite?oldid=1085641658&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Turmite-111180121010-12536.png wiki-commons:Special:FilePath/Turmite-120121010011-8342.png wiki-commons:Special:FilePath/Turmite-121021110111-27731.png wiki-commons:Special:FilePath/Turmite-121181121020-65932.png wiki-commons:Special:FilePath/Turmite-180121020081-223577.png wiki-commons:Special:FilePath/Turmite-181181121010-10211.png wiki-commons:Special:FilePath/Turmite_creating_a_growing_diamond.png wiki-commons:Special:FilePath/Hexagonal_turmite.jpg wiki-commons:Special:FilePath/Turmite_Snowflake.jpg |
| foaf:isPrimaryTopicOf | wikipedia-en:Turmite |
| is dbo:wikiPageRedirects of | dbr:Tur-mite dbr:Turmites |
| is dbo:wikiPageWikiLink of | dbr:Ant_(disambiguation) dbr:Busy_beaver dbr:Langton's_ant dbr:Cellular_automaton dbr:Greg_Turk dbr:Turing_machine dbr:Vant dbr:List_of_things_named_after_Alan_Turing dbr:Tur-mite dbr:Turmites |
| is foaf:primaryTopic of | wikipedia-en:Turmite |
