Tag system (original) (raw)
En informatique théorique, plus précisément en calculabilité, un système de tague (tag system en anglais) est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. C'est un cas particulier de système de Post. Ce modèle est Turing-complet : toute fonction calculable peut être représentée par un système de tague de Post.
| Property | Value |
|---|---|
| dbo:abstract | En informatique théorique, plus précisément en calculabilité, un système de tague (tag system en anglais) est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. C'est un cas particulier de système de Post. Ce modèle est Turing-complet : toute fonction calculable peut être représentée par un système de tague de Post. (fr) En teoría de la computación y , una máquina de Post, bautizada así en honor de Emil Leon Post, es un con una cola. No hay cinta de lectura separada. Al principio del cómputo, la cadena de entrada x es cargada en la cola. La cadena de entrada es seguida por un símbolo especial de fin de entrada. Al iniciarse el cómputo, la cola sólo contiene la configuración de entrada. El primer símbolo de x está al principio de la cola y el símbolo de final de entrada está luego del último carácter. Una máquina de transición de Post depende del símbolo al frente de la cola y del estado. Cada transición borrará el símbolo al principio de la cola. Una transición tiene dos componentes: el próximo estado y una cadena que se inserta al final de la cola. La cadena puede ser vacía. (es) A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post–Turing machines)—briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. Because all of the indicated operations are performed in a single transition, a tag machine strictly has only one state. (en) タグシステム（英: Tag system）は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械（Post Tag Machine、PTM）とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。 (ja) Na teoria da computação, uma máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar. Post publicou este modelo computacional em 1943 como uma forma simples de sistema canônico de Post. Em poucas palavras, uma máquina de estados finita cuja fila tem um tamanho ilimitado, tal que em cada transição a máquina lê o símbolo da cabeça da fila, remove um número fixo de símbolos da cabeça, e ao fim concatena uma palavra-símbolo pré-definida ao símbolo removido. (pt) 标记系统是 在1943年创立的确定性计算模型，作为一种简单形式的。标记系统也可以看作抽象机，叫做 Post 标记机（不要混淆于Post-图灵机）——简单的说，其唯一的磁带是无限长度的FIFO队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。 (zh) |
| dbo:wikiPageExternalLink | https://mathworld.wolfram.com/CyclicTagSystem.html https://mathworld.wolfram.com/TagSystem.html https://www.wolframscience.com/nks/p669/ https://www.wolframscience.com/nks/p95/ https://archive.org/details/computationfinit0000mins/page/267 https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/197 https://archive.org/details/sim_american-journal-of-mathematics_1943-04_65_2/page/203 https://www.sciencedirect.com/science/article/pii/S0304397507007700%7Cjournal=Theoretical |
| dbo:wikiPageID | 308891 (xsd:integer) |
| dbo:wikiPageLength | 15720 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124766162 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Decision_problem dbr:Collatz_conjecture dbr:Emil_Leon_Post dbr:Computational_model dbr:Surrogate_model dbr:Tag_(game) dbr:Post_canonical_system dbr:Halting_problem dbr:Hao_Wang_(academic) dbc:Models_of_computation dbr:Marvin_Minsky dbr:Post–Turing_machine dbr:Matthew_Cook dbr:Undecidable_problem dbr:Universal_Turing_machine dbr:FIFO_(computing_and_electronics) dbr:Queue_automaton dbr:Finite-state_machine dbr:Turing-complete dbr:Rule_110_cellular_automaton dbr:Emil_Post dbr:Queue_(data_structure) |
| dbp:wikiPageUsesTemplate | dbt:Jstor dbt:Cite_book dbt:Cite_journal dbt:Mono dbt:Sfrac |
| dcterms:subject | dbc:Models_of_computation |
| gold:hypernym | dbr:Model |
| rdf:type | dbo:Person yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | En informatique théorique, plus précisément en calculabilité, un système de tague (tag system en anglais) est un modèle de calculabilité défini par Emil Leon Post en 1943 comme système de réécriture. C'est un cas particulier de système de Post. Ce modèle est Turing-complet : toute fonction calculable peut être représentée par un système de tague de Post. (fr) En teoría de la computación y , una máquina de Post, bautizada así en honor de Emil Leon Post, es un con una cola. No hay cinta de lectura separada. Al principio del cómputo, la cadena de entrada x es cargada en la cola. La cadena de entrada es seguida por un símbolo especial de fin de entrada. Al iniciarse el cómputo, la cola sólo contiene la configuración de entrada. El primer símbolo de x está al principio de la cola y el símbolo de final de entrada está luego del último carácter. Una máquina de transición de Post depende del símbolo al frente de la cola y del estado. Cada transición borrará el símbolo al principio de la cola. Una transición tiene dos componentes: el próximo estado y una cadena que se inserta al final de la cola. La cadena puede ser vacía. (es) タグシステム（英: Tag system）は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械（Post Tag Machine、PTM）とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。 (ja) Na teoria da computação, uma máquina de Post, assim denominada em honra a Emil Leon Post, é um autômato determinístico, baseado na estrutura de dados do tipo fila com um símbolo auxiliar. Post publicou este modelo computacional em 1943 como uma forma simples de sistema canônico de Post. Em poucas palavras, uma máquina de estados finita cuja fila tem um tamanho ilimitado, tal que em cada transição a máquina lê o símbolo da cabeça da fila, remove um número fixo de símbolos da cabeça, e ao fim concatena uma palavra-símbolo pré-definida ao símbolo removido. (pt) 标记系统是 在1943年创立的确定性计算模型，作为一种简单形式的。标记系统也可以看作抽象机，叫做 Post 标记机（不要混淆于Post-图灵机）——简单的说，其唯一的磁带是无限长度的FIFO队列的有限状态自动机，在每次状态转变中机器读在队列头部的符号，从头部删除固定数目的符号，并可以向尾部增加符号。 (zh) A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of a Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine (not to be confused with Post–Turing machines)—briefly, a finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. (en) |
| rdfs:label | Máquina de Post (es) Système de tague (fr) タグシステム (ja) Máquina de Post (pt) Tag system (en) 标记系统 (zh) |
| owl:sameAs | freebase:Tag system yago-res:Tag system wikidata:Tag system dbpedia-es:Tag system dbpedia-fr:Tag system dbpedia-ja:Tag system dbpedia-pt:Tag system dbpedia-zh:Tag system https://global.dbpedia.org/id/31jkA |
| prov:wasDerivedFrom | wikipedia-en:Tag_system?oldid=1124766162&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Tag_system |
| is dbo:wikiPageDisambiguates of | dbr:Tag |
| is dbo:wikiPageRedirects of | dbr:Cyclic_tag dbr:Cyclic_Tag_System dbr:Cyclic_tag_system dbr:Tag_systems |
| is dbo:wikiPageWikiLink of | dbr:Computable_function dbr:Counter-machine_model dbr:Rule_90 dbr:Collatz_conjecture dbr:Emil_Leon_Post dbr:Rule_110 dbr:Zellig_Harris dbr:Tag dbr:Post_canonical_system dbr:Cyclic_tag dbr:Kolakoski_sequence dbr:Halting_problem dbr:A_New_Kind_of_Science dbr:Automatic_sequence dbr:Model_of_computation dbr:Universal_Turing_machine dbr:List_of_undecidable_problems dbr:Queue_automaton dbr:Wolfram's_2-state_3-symbol_Turing_machine dbr:Post_machine dbr:Cyclic_Tag_System dbr:Cyclic_tag_system dbr:Tag_systems |
| is foaf:primaryTopic of | wikipedia-en:Tag_system |