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 cuál 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.

rdfs:comment
  • 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 cuál 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)
foaf:isPrimaryTopicOf
rdfs:label
  • Turmite (es)
Is foaf:primaryTopic of
dcterms:subject
prov:wasDerivedFrom
dbpedia-owl:wikiPageID
  • 1637316 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 3934 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 15 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 64659237 (xsd:integer)
dbpedia-owl:wikiPageWikiLink [15 values]
Is dbpedia-owl:wikiPageWikiLink of