Turing machine equivalents (original) (raw)
A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm. While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model.
| Property | Value |
|---|---|
| dbo:abstract | A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm. While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model. (en) Uma máquina de Turing é um dispositivo teórico com uma capacidade de memória infinita, inicialmente concebida por Alan Turing em 1936. A máquina manipula símbolos em células de uma fita potencialmente infinita de acordo com uma função de transição, e pode ser adaptada para simular a lógica de qualquer algoritmo de computador. Embora nenhum dos seguintes modelos tenha sido demonstrado ter mais poder que o modelo de máquina de Turing de uma fita — infinita e multi-símbolo —, seus autores definiram e usaram tais máquinas para investigar questões e resolver problemas mais facilmente do que eles poderiam ter ao usar o modelo tradicional da máquina de Turing. (pt) |
| dbo:wikiPageID | 6263864 (xsd:integer) |
| dbo:wikiPageLength | 19066 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1089492945 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Wang_B-machine dbr:Peter_van_Emde_Boas dbr:DSPACE dbr:Corrado_Böhm dbr:Church–Turing_thesis dbr:Cook–Levin_theorem dbc:Turing_machine dbr:Structured_programming dbr:Markov_algorithm dbr:Gödel_numbering dbr:Alan_Turing dbr:Hao_Wang_(academic) dbc:Models_of_computation dbc:Theory_of_computation dbr:Lambda_calculus dbr:Post–Turing_machine dbr:Circuit_complexity dbr:Recursion_(computer_science) dbr:Turing_machine dbr:Von_Neumann_architecture dbr:Programming_language dbr:Queue_automaton dbr:Pointer_machine dbr:Turing_completeness dbr:Space_complexity dbr:Turing-complete dbr:Emil_Post dbr:P" dbr:Μ_recursion dbr:Sublinear |
| dbp:wikiPageUsesTemplate | dbt:Details dbt:EngvarB dbt:Mvar dbt:Reflist dbt:Short_description dbt:Tmath dbt:Use_dmy_dates dbt:Turing |
| dcterms:subject | dbc:Turing_machine dbc:Models_of_computation dbc:Theory_of_computation |
| gold:hypernym | dbr:Device |
| rdf:type | yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo dbo:Device yago:Whole100003553 |
| rdfs:comment | A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of rules, and they provide the theoretical underpinnings for the notion of a computer algorithm. While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model. (en) Uma máquina de Turing é um dispositivo teórico com uma capacidade de memória infinita, inicialmente concebida por Alan Turing em 1936. A máquina manipula símbolos em células de uma fita potencialmente infinita de acordo com uma função de transição, e pode ser adaptada para simular a lógica de qualquer algoritmo de computador. (pt) |
| rdfs:label | Máquinas de Turing equivalentes (pt) Turing machine equivalents (en) |
| owl:sameAs | freebase:Turing machine equivalents yago-res:Turing machine equivalents wikidata:Turing machine equivalents dbpedia-da:Turing machine equivalents dbpedia-fa:Turing machine equivalents dbpedia-pt:Turing machine equivalents https://global.dbpedia.org/id/4wkHq |
| prov:wasDerivedFrom | wikipedia-en:Turing_machine_equivalents?oldid=1089492945&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Turing_machine_equivalents |
| is dbo:wikiPageWikiLink of | dbr:Index_of_philosophy_articles_(R–Z) dbr:Computational_complexity_theory dbr:Algorithm_characterizations dbr:Counter_machine dbr:Read-only_Turing_machine dbr:Automata_theory dbr:Circuit_complexity dbr:Oblivious_RAM dbr:Universal_Turing_machine dbr:Queue_automaton dbr:Multitape_Turing_machine dbr:Parameterized_complexity dbr:Turing_equivalence |
| is rdfs:seeAlso of | dbr:Turing_machine |
| is foaf:primaryTopic of | wikipedia-en:Turing_machine_equivalents |