Diferencia entre revisiones de «Turmite»

Contenido eliminado Contenido añadido

En renglón

Revisión actual - 06:28 9 feb 2024

El turmite especificado como {{{1, 2, 0}, {1, 2, 1}}, {{0, 1, 0}, {0, 1, 1}}} se muestra en 8342 pasos de tiempo.

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 (recursivamente enumerables 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 $k$ cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con $k$ cintas (siendo $k$ el número mínimo con el cual se logre la máxima eficacia), o sea, aproximadamente en tiempo $O({\sqrt {n}})$ , siendo $n$ el tiempo en el que ese mismo problema es resuelto por una MT determinista de una sola cinta.

Definición formal

Un Turmite es una 7-tupla $T=(Q,\Sigma ,\Gamma ,s,b,F,\delta )\,$ , donde:

$Q\,$ es un conjunto finito de estados.
$\Sigma \subseteq \Gamma \,$ es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
$\Gamma \,$ es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
$s\in Q$ es el estado inicial.
$b\in \Gamma$ es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
$F\subseteq Q$ es el conjunto de estados finales de aceptación.
$\delta :Q\times \Gamma ^{k}\rightarrow Q\times \Gamma ^{k}\times \{L,S,R\}^{k}\,$ es una función parcial denominada función de transición, donde L es un movimiento a la izquierda, S indica un no-movimiento de cabeza y R es el movimiento a la derecha; k es el número de cabezas dentro de la cinta bidimensional.

Existen muchas definiciones válidas para un Turmite al igual que muchas otras para una MT, la diferencia entre un Turmite y una MT no radica tanto en la definición matemática utilizada para establecer una estipulación entre el humano y la representación abstracta, sino que se refleja pragmáticamente, es decir, cuándo hablamos de movimientos utilizaremos la misma notación que se utiliza para las MT´s de cintas múltiples (Tomando cada cinta de la MT multicinta como un marcador en el Turmite), con esto en mente, una configuración de un Turmite se denota:

$(q,(a$ $b$ $c)_{1},\cdots ,(a$ $b$ $c)_{k})$

donde $q$ es un estado del Turmite, $a$ y $c\in \Gamma ^{*}$ y $b\in \Gamma$ es donde está posicionada una de las $k$ cabezas.

Un grano de arena para la Tesis de Church-Turing

La siguiente aseveración, "Una MT ordinaria tiene el mismo poder (soslayando la eficacia) que un Turmite (MT con cinta bidimensional)" es verdadera, y aporta un grano de arena a una prueba constructiva de que la Tesis de Church-Turing es verdadera también, como también se demostró que sucede lo mismo con una MTN (MT no determinista), una Máquina de Post, un autómata finito con dos pilas, un autómata finito con pila y 2 marcadores, una MT con solo 2 estados, el Juego de la vida de John Conway, un autómata celular, una gramática formal y otros modelos de computación descubiertos (y aún por descubrir) no hipotéticos, todos ellos tienen el mismo poder que una MT y, en virtúd de la propiedad transitiva de la relación "el mismo poder", el mismo poder que un Turmite lo que constituyen una forma más o menos fidedigna de probar que esta Tesis es verdadera.

Véase también

Problema de la parada (Un problema insoluble para una MT, y por lo antedicho, insoluble para un Turmite)

Datos: Q3099136
Multimedia: Turmite / Q3099136

@@ Línea 1: / Línea 1: @@
+[[Archivo:Turmite-120121010011-8342.png|miniaturadeimagen|El turmite especificado como {<nowiki>{{1, 2, 0}, {1, 2, 1}}</nowiki>, <nowiki>{{0, 1, 0}, {0, 1, 1}}</nowiki>} se muestra en 8342 pasos de tiempo.]]
-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 <math>k</math> cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con <math>k</math> cintas (siendo <math>k</math> el número mínimo con el cuál se logre la máxima eficacia), o sea, aproximadamente en tiempo <math>O(\sqrt n)</math>, siendo <math>n</math> el tiempo en el que ese mismo problema es resuelto por una MT determinista de una sóla cinta.
+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 ([[Lenguaje recursivamente enumerable|recursivamente enumerables]] y [[Lenguaje recursivo|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 <math>k</math> cabezas resuelve un problema exactamente en el mismo tiempo que lo resuelve una MT con <math>k</math> cintas (siendo <math>k</math> el número mínimo con el cual se logre la máxima eficacia), o sea, aproximadamente en tiempo <math>O(\sqrt n)</math>, siendo <math>n</math> el tiempo en el que ese mismo problema es resuelto por una MT determinista de una sola cinta.
 == Definición formal ==
@@ Línea 5: / Línea 6: @@
 Un '''Turmite''' es una 7-[[tupla]] <math>T=(Q, \Sigma, \Gamma, s, b, F, \delta)\,</math>, donde:
-*<math>Q \,</math> es un conjunto finito de [[Estado físico|estados]].
+* <math>Q \,</math> es un [[conjunto finito]] de [[Estado físico|estados]].
-*<math>\Sigma \subseteq \Gamma \,</math> es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
+* <math>\Sigma \subseteq \Gamma \,</math> es un conjunto finito de símbolos de entrada, el alfabeto de entrada.
-*<math>\Gamma \,</math> es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
+* <math>\Gamma \,</math> es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
-*<math>s \in Q</math> es el estado inicial.
+* <math>s \in Q</math> es el estado inicial.
-*<math>b \in \Gamma</math> es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
+* <math>b \in \Gamma</math> es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
-*<math>F \subseteq Q</math> es el conjunto de estados finales de aceptación.
+* <math>F \subseteq Q</math> es el conjunto de estados finales de aceptación.
-*<math>\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,S,R\}^k\,</math> es una [[función parcial]] denominada función de transición, donde L es un movimiento a la izquierda, S indica un no-movimiento de cabeza y R es el movimiento a la derecha; k es el número de cabezas dentro de la cinta bidimensional.
+* <math>\delta: Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L,S,R\}^k\,</math> es una [[función parcial]] denominada función de transición, donde L es un movimiento a la izquierda, S indica un no-movimiento de cabeza y R es el movimiento a la derecha; k es el número de cabezas dentro de la cinta bidimensional.
-Existen muchas definiciones válidas para un Turmite al igual que muchas otras para una MT, la diferencia entre un Turmite y una MT no radica tanto en la definición matemática utilizada para establecer una estipulación entre el humano y la representación abstracta, sino que se refleja pragmáticamente, es decir, cuándo hablamos de movimientos utilizaremos la misma notación que se utiliza para las MT´s de cintas multiples (Tomando cada cinta de la MT multicinta como un marcador en el Turmite), con esto en mente, una configuración de un Turmite se denota:
+Existen muchas definiciones válidas para un Turmite al igual que muchas otras para una MT, la diferencia entre un Turmite y una MT no radica tanto en la definición matemática utilizada para establecer una estipulación entre el humano y la representación abstracta, sino que se refleja pragmáticamente, es decir, cuándo hablamos de movimientos utilizaremos la misma notación que se utiliza para las MT´s de cintas múltiples (Tomando cada cinta de la MT multicinta como un marcador en el Turmite), con esto en mente, una configuración de un Turmite se denota:
-<math>(q,(a</math><s><math>b</math></s><math>c)_1, \cdots ,(a</math><s><math>b</math></s><math>c)_k)</math>
+<math>(q,(a</math><math>b</math><small><math>c)_1, \cdots ,(a</math></small><math>b</math><math>c)_k)</math>
+donde <math>q</math> es un estado del Turmite, <math>a</math> y <math>c \in \Gamma^*</math> y <math>b \in \Gamma</math> es donde está posicionada una de las <math>k</math> cabezas.
 == Un grano de arena para la Tesis de Church-Turing ==
-La siguiente aseveración, "Una MT ordinaria tiene el mismo poder (soslayando la eficacia) que un Turmite (MT con cinta bidimensional)" es verdadera, y aporta un grano de arena a una prueba constructiva de que la [[Tesis de Church-Turing]] es verdadera también, como también se demostró que sucede lo mismo con una MTN (MT no determinista), una [[Máquina de Post]], un autómata finito con dos pilas, un autómata finito con pila y 2 marcadores, una MT con sólo 2 estados, el [[Juego de la vida]] de [[John Conway]], un [[autómata celular]], una [[gramática formal]] y otros modelos de computación descubiertos (y aún por descubrir) no hipotéticos, todos ellos tienen el mismo poder que una MT y, en virtúd de la propiedad transitiva de la relación "el mismo poder", el mismo poder que un [[Turmite]] lo que constituyen una forma más o menos fidedigna de probar que esta Tesis es verdadera.
+La siguiente aseveración, "Una MT ordinaria tiene el mismo poder (soslayando la eficacia) que un Turmite (MT con cinta bidimensional)" es verdadera, y aporta un grano de arena a una prueba constructiva de que la [[Tesis de Church-Turing]] es verdadera también, como también se demostró que sucede lo mismo con una MTN (MT no determinista), una [[Máquina de Post]], un [[autómata finito]] con dos pilas, un autómata finito con pila y 2 marcadores, una MT con solo 2 estados, el [[Juego de la vida]] de [[John Horton Conway|John Conway]], un [[autómata celular]], una [[gramática formal]] y otros [[Modelo de computación|modelos de computación]] descubiertos (y aún por descubrir) no hipotéticos, todos ellos tienen el mismo poder que una MT y, en virtúd de la propiedad transitiva de la relación "el mismo poder", el mismo poder que un Turmite lo que constituyen una forma más o menos fidedigna de probar que esta Tesis es verdadera.
 == Véase también ==
@@ Línea 25: / Línea 28: @@
 * [[Problema de la parada]] (Un problema insoluble para una MT, y por lo antedicho, insoluble para un Turmite)
+{{Control de autoridades}}
-[[Categoría:Computabilidad]]
 [[Categoría:Máquinas de Turing]]
-[[en:Turmite]]
-[[fr:Turmite]]
-[[pl:Turmity]]