| dbo:abstract
|
- Una màquina de Turing multipista és una màquina de Turing que té múltiples cintes. Cada cinta té el seu propi capçal per llegir o escriure. Inicialment l'entrada apareix a la cinta número 1 i la resta comencen buides. Tot i aquest model sembla molt més potent que una màquina de Turing tradicional amb una sola cinta, qualsevol màquina amb una sola cinta pot simular una màquina multi-cinta (sense importar el nombre de cintes) utilitzant només un temps quadràtic respecte al temps original. Per tant, una màquina multicinta no pot calcular cap altre funció que no pugui calcular una màquina amb una sola cinta i cap de les classes de complexitat es veuen afectades per l'increment en el nombre de cintes de la màquina. (ca)
- Eine Mehrband-Turingmaschine (englisch Multitape Turing machine) ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine. Die Mehrband-Turingmaschine verfügt über mehrere Speicherbänder, die jeweils einen eigenen Lese- und Schreibkopf besitzen, wobei diese Lese- und Schreibköpfe unabhängig voneinander bewegt werden können (ein wesentlicher Unterschied zur Mehrspuren-Turingmaschine). Ansonsten verhält sich eine Mehrband-Turingmaschine genau so wie eine klassische Turingmaschine. Eine Mehrband-Turingmaschine mit nur einem Band entspricht genau der klassischen Turingmaschine und jede Mehrband-Turingmaschine kann durch eine klassische Turingmaschine (mit nur einem Band) simuliert werden. Die beiden Maschinenmodelle sind also bezüglich der Berechenbarkeit von Funktionen äquivalent, d. h., beide Modelle können die gleichen Funktionen berechnen. Die Mehrband-Turingmaschine arbeitet im Allgemeinen effizienter als eine Einband-Maschine, aber nicht entscheidend im Sinne der wichtigsten Fragen der Komplexitätstheorie, d. h., vor allem für die Frage, welche Probleme in Polynomialzeit gelöst werden können: Eine Mehrband-Maschine, die ein Problem in Polynomialzeit löst, kann von einer Einband-Maschine in Polynomialzeit simuliert werden, wobei aber im Allgemeinen der Grad des die Laufzeit beschränkenden Polynoms höher ist. (de)
- A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank. This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine—no matter how many tapes—can be simulated by a single-tape machine using only quadratically more computation time. Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines. (en)
- Wielotaśmowa maszyna Turinga (ang. multitape Turing machine) jest jak zwykła maszyna Turinga z tą różnicą, że ma wiele taśm. Każda taśma ma własną głowicę do zapisu i odczytu danych. Początkowo dane wejściowe zapisane są na taśmie pierwszej, a pozostałe taśmy są puste. W niektórych publikacjach naukowych wielotaśmowa maszyna Turinga nazywana jest także maszyną Turinga z wieloma ciągami i kursorami, gdzie ciągi to innymi słowy taśmy, natomiast kursory to głowice. Każdą wielotaśmową maszynę Turinga działającą w czasie niezależnie od liczby taśm, można zasymulować za pomocą jednotaśmowej maszyny Turinga w czasie . Ponadto żadna z klas złożoności (np. czasu wielomianowego) nie podlega zmianom, a zatem zarówno w modelu jednotaśmowym, jak i wielotaśmowym są one takie same. (pl)
- Uma máquina de Turing multifita é uma máquina de Turing comum com várias fitas. Inicialmente a entrada aparece na fita 1 e todas as outras vazias, como cada fita tem sua própria cabeça para ler e escrever, a função de transição pode ler, escrever e mover as cabeças em algumas ou todas as fitas simultaneamente. (pt)
- 多带图灵机和图灵机类似，唯一的不同在于它可以有 条纸带，每条纸带上都有一个读写头。其状态转移函数 修改为： 此处 是带子的数目。表达式 其中 = L 或 R，说明若机器处于状态 ，读写头 所读出的符号分别为，则转移到新状态 ，将读写头 下的符号分别修改为 ，并将读写头 按照 所指示的方向移动， 读写头 向左移， 读写头 向右移。 可以证明，对于任意一个多带图灵机 ，存在一个单带图灵机 ，满足 。 (zh)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3606 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Uma máquina de Turing multifita é uma máquina de Turing comum com várias fitas. Inicialmente a entrada aparece na fita 1 e todas as outras vazias, como cada fita tem sua própria cabeça para ler e escrever, a função de transição pode ler, escrever e mover as cabeças em algumas ou todas as fitas simultaneamente. (pt)
- 多带图灵机和图灵机类似，唯一的不同在于它可以有 条纸带，每条纸带上都有一个读写头。其状态转移函数 修改为： 此处 是带子的数目。表达式 其中 = L 或 R，说明若机器处于状态 ，读写头 所读出的符号分别为，则转移到新状态 ，将读写头 下的符号分别修改为 ，并将读写头 按照 所指示的方向移动， 读写头 向左移， 读写头 向右移。 可以证明，对于任意一个多带图灵机 ，存在一个单带图灵机 ，满足 。 (zh)
- Una màquina de Turing multipista és una màquina de Turing que té múltiples cintes. Cada cinta té el seu propi capçal per llegir o escriure. Inicialment l'entrada apareix a la cinta número 1 i la resta comencen buides. (ca)
- Eine Mehrband-Turingmaschine (englisch Multitape Turing machine) ist eine abstrakte Maschine in der theoretischen Informatik und eine Erweiterung der klassischen Turingmaschine. Die Mehrband-Turingmaschine verfügt über mehrere Speicherbänder, die jeweils einen eigenen Lese- und Schreibkopf besitzen, wobei diese Lese- und Schreibköpfe unabhängig voneinander bewegt werden können (ein wesentlicher Unterschied zur Mehrspuren-Turingmaschine). Ansonsten verhält sich eine Mehrband-Turingmaschine genau so wie eine klassische Turingmaschine. (de)
- A multi-tape Turing machine is a variant of the Turing machine that utilizes several tapes. Each tape has its own head for reading and writing. Initially, the input appears on tape 1, and the others start out blank. (en)
- Wielotaśmowa maszyna Turinga (ang. multitape Turing machine) jest jak zwykła maszyna Turinga z tą różnicą, że ma wiele taśm. Każda taśma ma własną głowicę do zapisu i odczytu danych. Początkowo dane wejściowe zapisane są na taśmie pierwszej, a pozostałe taśmy są puste. W niektórych publikacjach naukowych wielotaśmowa maszyna Turinga nazywana jest także maszyną Turinga z wieloma ciągami i kursorami, gdzie ciągi to innymi słowy taśmy, natomiast kursory to głowice. (pl)
|
| rdfs:label
|
- Màquina de Turing multicinta (ca)
- Mehrband-Turingmaschine (de)
- Multitape Turing machine (en)
- Wielotaśmowa maszyna Turinga (pl)
- Máquina de Turing multifita (pt)
- 多带图灵机 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
