Counter machine (original) (raw)
Une machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky.
| Property | Value |
|---|---|
| dbo:abstract | A counter machine is an abstract machine used in a formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorithms may be designed in such a matter to avoid interlocking, the simultaneous writing operation by two (or more) threads to the same memory address. (en) Une machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky. (fr) Maszyna licznikowa – abstrakcyjny model maszyny będący prostą odmianą maszyny rejestrowej. Najprostsza jej wersja zawiera dwie komendy: INC(R,Z), która zwiększa zawartość rejestru R o 1 i przechodzi do komendy Z oraz DEC(R,Z1,Z2), która zmniejsza zawartość rejestru R o 1 i przechodzi do komendy Z1, jeśli zawartość rejestru jest większa niż 0. Jeśli rejestr R zawiera zero to komenda nie zmienia jego zawartości i automatycznie przechodzi do komendy Z2. (pl) 計數器機（英語：Counter machine）是一種抽象機器，作为用于形式逻辑和理论计算机科学中的计算模型，计数器机是寄存器机模型的最原始的子类。 它只由如下组成：(i)一序列的一个或多个(唯一性)命名的“无界”寄存器(只包含一个单一无界正整数的寄存器)，(ii)假如到或减去自寄存器的叫做“计数器”的物件，(iii)让计算机(人或机器)服从的(通常顺序的)算术和控制指令的列表。 对于给定的计数器机模型，指令集是非常微小的，只有从 1 到 6 或 7 指令。所有模型都包含一些算术运算和至少一个“条件表达式”(IF-THEN-ELSE)。三个基本模型，每个都使用了三个指令，从下列指令中划分出来(简写助记符是任意的): * CLR ( r ): 清除(CLeaR)寄存器 'r' [清空计数器 'r'] * INC ( r ): 增加(INCrement)寄存器 'r' 的内容 * DEC ( r ): 减少(DECrement)寄存器 'r' 的内容 * CPY ( rj, rk ): 复制(CoPY)寄存器 rj 的内容到寄存器 rk，保持 rj 的内容不动 * JZ ( r, z ): 如果寄存器 'r' 的内容为零(Zero)，则跳转(Jump)到标记为 'z' 的指令，否则继续按顺序执行 * JE ( rj, rk, z ): 如果寄存器 rj 的内容等于(Equal)寄存器 rk 的内容，则跳转(Jump)到标记为 'z' 的指令，否则继续按顺序执行， * 集合 (1): { INC ( r ), DEC ( r ), JZ ( r, z ) }, ( Minsky (1961, 1967), Lambek (1961) ) * 集合 (2): { CLR ( r ), INC ( r ), JE ( rj, rk, z ) }, ( Ershov (1958), Peter (1958) 由 Shepherdson-Sturgis (1964) 解释; Minsky (1967); Schönhage (1980) ) * 集合 (3): { INC ( r ), CPY ( rj, rk ), JE ( rj, rk, z ) }, ( Elgot-Robinson (1964), Minsky (1967) )。 停机(HALT)指令可以包含也可以不包含在模型中。 三个计数器机的计算能力是等价的 -- 一个模型的指令可以从其他模型的指令得出。都等价于图灵机的计算能力(但只有用哥德尔数来编码在计算器中的数据，否则它们的能力等价于原始递归函数)。由于它们的一元处理方式，计数器典型的要比图灵机慢一个因子，它是在相比较的图灵机使用的空间的指数。 计数器机模型还有一些其他的名字: Shepherdson-Sturgis 机, Minsky 机, 程序机, 算盘机, Lambek 机, 后继机 等等。详情参见。 (zh) |
| dbo:wikiPageExternalLink | http://www.igblan.free-online.co.uk/igblan/ca/minsky.html https://archive.org/details/computationfinit0000mins https://archive.org/details/introductiontoau00hopc |
| dbo:wikiPageID | 7583543 (xsd:integer) |
| dbo:wikiPageLength | 54523 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114685990 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Primitive_recursive_function dbr:Schönhage dbr:Wang_B-machine dbr:John_P._Burgess dbr:John_von_Neumann dbr:Peter_van_Emde_Boas dbr:Remainder dbr:Richard_Jeffrey dbr:Space_hierarchy_theorem dbr:Computer dbr:One-instruction_set_computer dbr:Turing_machine_equivalents dbr:Μ_operator dbr:George_Boolos dbr:Gordon_Bell dbr:Andrey_Ershov dbr:Stephen_Cook dbr:Stephen_Kleene dbr:Computer_program dbr:Theoretical_computer_science dbr:Abraham_Robinson dbr:Allen_Newell dbr:Factorization dbc:Register_machines dbr:Frances_Yao dbr:Halting_problem dbr:Hans_Hermes dbr:Hao_Wang_(academic) dbr:Harvard_architecture dbr:Herman_Goldstine dbr:Jan_van_Leeuwen dbr:Prime_number dbr:Arthur_Burks dbr:Abstract_machine dbr:Joachim_Lambek dbr:Register_machine dbr:Stack_(data_structure) dbr:Donald_Knuth dbr:Martin_Davis_(mathematician) dbr:Marvin_Minsky dbr:Post–Turing_machine dbr:Integer dbr:Odd_number dbr:Canadian_Mathematical_Bulletin dbr:Random-access_machine dbr:Recursion_(computer_science) dbr:Model_of_computation dbr:Turing_machine dbr:Rózsa_Péter dbr:Universal_Turing_machine dbr:Formal_logic dbr:Pointer_machine dbr:Time_hierarchy_theorem dbr:Turing_tarpit dbr:Turing_completeness dbr:Finite_state_machine dbr:Register-machine_model dbr:Rich_Schroeppel dbr:Partial_recursive_function dbr:Primitive_recursion dbr:Gödel_number dbr:Calvin_Elgot dbr:H._E._Sturgis dbr:J._Hartmanis dbr:John_C._Shepherdson dbr:Z._A._Melzak |
| dbp:title | Register machine (en) |
| dbp:urlname | RegisterMachine (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Cite_journal dbt:ISBN dbt:Main dbt:MathWorld dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Register_machines |
| gold:hypernym | dbr:Machine |
| rdf:type | dbo:Software yago:Artifact100021939 yago:Device103183080 yago:Instrumentality103575240 yago:Machine103699975 yago:Object100002684 yago:PhysicalEntity100001930 yago:Whole100003553 yago:WikicatRegisterMachines |
| rdfs:comment | Une machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky. (fr) Maszyna licznikowa – abstrakcyjny model maszyny będący prostą odmianą maszyny rejestrowej. Najprostsza jej wersja zawiera dwie komendy: INC(R,Z), która zwiększa zawartość rejestru R o 1 i przechodzi do komendy Z oraz DEC(R,Z1,Z2), która zmniejsza zawartość rejestru R o 1 i przechodzi do komendy Z1, jeśli zawartość rejestru jest większa niż 0. Jeśli rejestr R zawiera zero to komenda nie zmienia jego zawartości i automatycznie przechodzi do komendy Z2. (pl) A counter machine is an abstract machine used in a formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorit (en) 計數器機（英語：Counter machine）是一種抽象機器，作为用于形式逻辑和理论计算机科学中的计算模型，计数器机是寄存器机模型的最原始的子类。 它只由如下组成：(i)一序列的一个或多个(唯一性)命名的“无界”寄存器(只包含一个单一无界正整数的寄存器)，(ii)假如到或减去自寄存器的叫做“计数器”的物件，(iii)让计算机(人或机器)服从的(通常顺序的)算术和控制指令的列表。 对于给定的计数器机模型，指令集是非常微小的，只有从 1 到 6 或 7 指令。所有模型都包含一些算术运算和至少一个“条件表达式”(IF-THEN-ELSE)。三个基本模型，每个都使用了三个指令，从下列指令中划分出来(简写助记符是任意的): 停机(HALT)指令可以包含也可以不包含在模型中。 三个计数器机的计算能力是等价的 -- 一个模型的指令可以从其他模型的指令得出。都等价于图灵机的计算能力(但只有用哥德尔数来编码在计算器中的数据，否则它们的能力等价于原始递归函数)。由于它们的一元处理方式，计数器典型的要比图灵机慢一个因子，它是在相比较的图灵机使用的空间的指数。 计数器机模型还有一些其他的名字: Shepherdson-Sturgis 机, Minsky 机, 程序机, 算盘机, Lambek 机, 后继机 等等。详情参见。 (zh) |
| rdfs:label | Counter machine (en) Machine à compteurs (fr) Maszyna licznikowa (pl) 计数器机 (zh) |
| owl:sameAs | freebase:Counter machine yago-res:Counter machine wikidata:Counter machine dbpedia-fr:Counter machine dbpedia-pl:Counter machine dbpedia-zh:Counter machine https://global.dbpedia.org/id/4wRoF |
| prov:wasDerivedFrom | wikipedia-en:Counter_machine?oldid=1114685990&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Counter_machine |
| is dbo:wikiPageDisambiguates of | dbr:Counter |
| is dbo:wikiPageWikiLink of | dbr:Propositional_formula dbr:Patrick_C._Fischer dbr:Counter-machine_model dbr:Μ_operator dbr:Church–Turing_thesis dbr:Counter dbr:Algorithm_characterizations dbr:Cell-probe_model dbr:Counter_(digital) dbr:Hybrid_automaton dbr:LOOP_(programming_language) dbr:Register_machine dbr:Random-access_machine dbr:Turing_machine dbr:Richard_Schroeppel dbr:Universal_Turing_machine dbr:Pointer_machine |
| is foaf:primaryTopic of | wikipedia-en:Counter_machine |