{"entities":{"Q792760":{"pageid":794608,"ns":120,"title":"Item:Q792760","lastrevid":64375857,"modified":"2026-04-11T19:26:43Z","type":"item","id":"Q792760","labels":{"en":{"language":"en","value":"Simple programming languages and restricted classes of Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3854418"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$65C21F67-6215-48D6-9154-316234F0B19C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4ea3a2f934c9e9f1bbd178c50247a14bb2e16b18","datavalue":{"value":{"text":"Simple programming languages and restricted classes of Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792760$2E0FF76F-2F09-405F-A24C-930EA6A158C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05e8cd7a6d19bfc261fe77fdc2235beaa0a68b1c","datavalue":{"value":"0537.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$BA6D5B4D-2E91-4EDE-BA34-4326A6E44213","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41191b88bc0518b9a0bea1c797f647fef8692ac7","datavalue":{"value":"10.1016/0304-3975(83)90085-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$3BFD3EBB-1AF4-4C7E-844D-FD3037CDC0A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0ccf6eb6c37793d5bd821ffa019f577d6c7be3b","datavalue":{"value":{"entity-type":"item","numeric-id":243823,"id":"Q243823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$2A246587-17F4-4EF6-810F-FDFB33301A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fbe9a2f35bfbb97131fdd4f5f88a8af0c602f0","datavalue":{"value":{"entity-type":"item","numeric-id":688713,"id":"Q688713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$427A5058-EF1A-4167-9931-F226D2F477F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$75121D71-E460-439F-BF8A-9D3E3F36E5D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q792760$738A4D5B-3D0E-4D3C-80CE-33B8AB716FD1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"11038415e791886823c78ae9a68f3b79cfb2963a","datavalue":{"value":"The computational power of simple programming languages is investigated and characterisations (or partial characterisations) of the functions computable by such programs are given in terms of some space and/or time complexity classes of Turing machines. Calling a function \\(f(x_ 1,...x_ t)\\) over the nonnegative integers linearly bounded (LBF) if \\(f(x_ 1,...,x_ t)\\leq 0(x_ 1+...+x_ t),\\) it is shown that any LBF computable by a Turing machine in 0(n) space and \\(0(2^{\\lambda n})\\) time, where \\(\\lambda<1\\) and n is the length of the binary representation of \\(x_ 1+...+x_ t,\\) can be computed by a program without nested loops using only the instruction set \\(R=\\{x\\leftarrow x\\dot-1\\), if \\(x=0\\) then \\(y\\leftarrow y+1\\), do \\(x...\\) end\\}. Thus, functions like \\(\\lfloor x/y\\rfloor\\), \\(\\gcd \\{x,y\\}\\), \\(\\lfloor^ k\\sqrt{x}\\rfloor\\), \\(\\lfloor \\log x\\rfloor\\), etc. can be computed by R-programs. Any function computable by an R-program can be computed by a Turing machine in \\(0(n)\\) space and \\(0(2^ n)\\) time. It is open whether or not the time can be reduced to \\(0(2^{\\lambda n})\\) for some \\(\\lambda<1\\) (which may depend on the program). Simple programming languages are also introduced which are complete characterisations of the functions computable by certain space bounded (linear bounded, polynomial bounded, etc.) classes of Turing machines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792760$6F7E69BA-0B3E-49E7-B2FF-63285DB808C9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dd04b5fb2c3323ec3474b39a7302f6dfaf7fdf92","datavalue":{"value":{"entity-type":"item","numeric-id":792759,"id":"Q792759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$E421D924-37E5-4277-A5CD-B2CE80EA3183","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$920A385C-BA12-4DCF-82D9-5D817A8B4B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$D2CFB2F7-7BD6-47C6-B97C-4652E350BDBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$D4F597A0-D8D1-4DA3-A3E2-95C1CC7CE687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$101026FC-75C2-4A73-80B0-F5F6D922E105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$4EE7B03B-9AA8-4684-B105-84C1CD76E375","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd4313ee1f4fc9d87f964e59d0f85b50a90f0738","datavalue":{"value":"3854418","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$58D4D38F-8968-49E6-852A-9747A03A8C9A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"18bd66fa418c5cb5068afda24262698a2b821b67","datavalue":{"value":"computational power of simple programming languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q792760$F183B450-D4E3-47DE-A4EB-44731C9AAE2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eea487d88e020f1290158d615297a1c9e63917b7","datavalue":{"value":"complexity classes of Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q792760$F135584C-B63F-4672-96DC-1EF81E5DA8D5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$DE41BC35-CEEC-48F5-809F-EE2E44653F0D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"18e49f0e5d8f6962a546a350a3668c8745314642","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90085-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q792760$9DA6DA77-1E2F-463D-87F4-3F3EFCA23A55","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a28b1dcabd51abfc9bea6850b1d73116774f0066","datavalue":{"value":"W2009880057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792760$AD608DC5-B274-4C4F-9004-D5AD418ACD87","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2197e3ded5db1cf75fdc16bcdc622a4ef6039ad","datavalue":{"value":{"entity-type":"item","numeric-id":3906420,"id":"Q3906420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$E5B950E7-51B5-45F8-87E9-E93EF208AA6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddc9bd4aabffec9f71c59e32f3f5dd827f8b9d16","datavalue":{"value":{"entity-type":"item","numeric-id":4124274,"id":"Q4124274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$DF9FEE5F-91D7-4922-8557-764361FFC60F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d18c026883c4f66096e389fd3ca726dc1282151","datavalue":{"value":{"entity-type":"item","numeric-id":4170194,"id":"Q4170194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$D2E41A40-138B-497A-83DB-00EF14F87133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0472dbb9460a41709f6cf9fbcdb326f4bea9d4d7","datavalue":{"value":{"entity-type":"item","numeric-id":5551469,"id":"Q5551469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$8DF78CDC-9218-470A-B03C-31FC5441191B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4decfe4a9dcd7ae73a351b5c9e4e8672c09185c","datavalue":{"value":{"entity-type":"item","numeric-id":1394128,"id":"Q1394128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$B412BCD9-91B3-4707-9A52-5660DE424059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ff5e5ed9a47676d1f71c039408d4e7152ada392","datavalue":{"value":{"entity-type":"item","numeric-id":3912019,"id":"Q3912019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$F8C02A63-04CF-40A6-8F87-7995209CA95B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"354e7fee535f06b18b96c8fbf1ea2b4be609b212","datavalue":{"value":{"entity-type":"item","numeric-id":3664434,"id":"Q3664434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$4566135F-5F1E-49ED-8F0E-EE07EBF545E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ab4fbdb360439f643f558ce6b709b490cf1e1","datavalue":{"value":{"entity-type":"item","numeric-id":1137991,"id":"Q1137991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$222EB63B-819A-44D1-ADEE-D0EAF92CEAE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$9845C4A9-0F53-4588-AE00-13EE9979B260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33b7f307448469f1fcba46c332f76bc8363b3674","datavalue":{"value":{"entity-type":"item","numeric-id":4162478,"id":"Q4162478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$668F2D22-2706-4F70-83CF-0B098A7F1E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eafb225ff1a1521cdfa086c2196aa154fa518299","datavalue":{"value":{"entity-type":"item","numeric-id":5609377,"id":"Q5609377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792760$3393B2E0-09EE-4FE0-BADB-60CAC2AD95B7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bbd6e546dee7200ac643fdb8582348d6f2c7ce5","datavalue":{"value":{"entity-type":"item","numeric-id":5292648,"id":"Q5292648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94e42c7a02e643db9cb87a3267c2917dd12cfab5","datavalue":{"value":{"amount":"+0.8036863803863525","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q792760$30FBD256-8B75-4580-837D-855301A8EFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85ee3035903d354ab6d7c9365a93a3f201dd2507","datavalue":{"value":{"entity-type":"item","numeric-id":1827396,"id":"Q1827396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b03b39213e0c77e7ba4d4282ecd24f9fa80aa8fc","datavalue":{"value":{"amount":"+0.780771791934967","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q792760$2D60755E-1966-43CB-877A-0B1EE50D084F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd37efe72d7a2a5cc948dcbce447e33d0c8c58a0","datavalue":{"value":{"entity-type":"item","numeric-id":1575880,"id":"Q1575880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0274f1ac07d77f9a559dd787517ae8dfebe76b5","datavalue":{"value":{"amount":"+0.7785568833351135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q792760$9F7BCD8A-A750-4910-B7C9-002B91DC6CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"394addeaeeb72fb98deebc6b6872ee27e9db5855","datavalue":{"value":{"entity-type":"item","numeric-id":5687659,"id":"Q5687659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"115d581ce5ceb564f50b832754b5afbb7c28dbf4","datavalue":{"value":{"amount":"+0.7725249528884888","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q792760$56773B49-B5E1-4F47-8D1E-2A2A049B6857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f6b115f9c89b580b6d04fe96e58b8fd6bbfb329","datavalue":{"value":{"entity-type":"item","numeric-id":3694665,"id":"Q3694665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44c5309dae648883d40c253865635c575132ffbc","datavalue":{"value":{"amount":"+0.7713971138000488","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q792760$C07F00CB-2610-4CD6-A719-3F46582240BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Simple programming languages and restricted classes of Turing machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Simple_programming_languages_and_restricted_classes_of_Turing_machines"}}}}}