{"entities":{"Q789180":{"pageid":791028,"ns":120,"title":"Item:Q789180","lastrevid":64431081,"modified":"2026-04-11T19:49:48Z","type":"item","id":"Q789180","labels":{"en":{"language":"en","value":"Unbounded hardware is equivalent to deterministic Turing machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845056"}},"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":"Q789180$71C3514C-0E00-4C6D-B8ED-FC26EABB9C2B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"58b2afd285878a3fa17c06feb4f88ec561a006a3","datavalue":{"value":{"text":"Unbounded hardware is equivalent to deterministic Turing machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789180$20375FD8-D304-45D1-AE5B-C32F117C1368","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8586247b088b5a2114007e1e27127033e2afe877","datavalue":{"value":"0532.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$0E8E6B9C-A280-481A-864B-D2E58D8EAB1B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"59248c955a91b337b05c4957bee54aa09e5223ab","datavalue":{"value":"10.1016/0304-3975(83)90044-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$4A06DE25-7409-4BE6-85ED-97DD6A905579","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ad91bd4a1378a015ef9d0cfb2ca621b16347f71","datavalue":{"value":{"entity-type":"item","numeric-id":525971,"id":"Q525971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$5C9431F8-5E27-47BC-9CAD-7DFA69191C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8e168b1e3b63593812ae7da58e47d8ceb56360b","datavalue":{"value":{"entity-type":"item","numeric-id":789178,"id":"Q789178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$25B6A2C6-5AB6-46E9-93D2-6D96FCC2B317","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":"Q789180$3C4934D8-FEF0-4A60-A1C5-2C7B642AF742","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":"Q789180$487202F8-A04F-48A0-B212-0FC23BA5A256","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7fc6fe04baf29960bc350c8a9106920a841b990","datavalue":{"value":"Unter Annahme einer physikalisch bedingten unteren Grenze f\u00fcr die Signallaufzeit simulieren die Verf. eine planare physikalische Schaltung durch eine funktionelle deterministische Turing-Maschine und umgekehrt in Polynomzeit. Damit verweisen sie Hoffnungen, durch Einsatz massiver paralleler Hardware NP-schwere Probleme generell in Polynomzeit zu ''knacken'', in das gro\u00dfe Reich physikalischer Absurdit\u00e4ten. Die durch Parallelarbeit m\u00f6glichen Effizienzgewinne sind in dem Modell der Verf. durch ''systolische'' Anordnungen zu erreichen, bei denen ''Schaltungsinseln'' sequentiell vor sich hin arbeiten und nur in gro\u00dfen Zeitabst\u00e4nden sparsam kommunizieren.","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$A9282874-130E-4F98-B12C-18FA97D665C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$468DA758-4A03-44AB-B856-D3A2474BF866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$A03A0652-218B-491A-BD17-C34C956BE2B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b3bac62a7edcf863bf6093798bbca3c77ee6bd0","datavalue":{"value":"3845056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$B6E880FB-A609-46E0-8E18-4D3C3660A27E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d401f2ace84898a4ed7a427e3e515e5751985090","datavalue":{"value":"deterministic Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$92214163-6C1D-4E8F-A2F6-CA3C68703D6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$7A268DFB-3BC5-4AD8-8965-69C6DF8B8E41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fe1e8f676040b787c7abd649c68d227da93e5c2","datavalue":{"value":"models of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$EA8B1AE3-3986-4B69-A716-C6256814857F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f543c9952559c111d4a96995c59b1fe2cdc39486","datavalue":{"value":"physical computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$A7EA3AD7-DBA2-40F2-A182-369AB59287EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f63e0ba119eaa2cd29c46a23e128902ce8d61ac9","datavalue":{"value":"planar digital circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$731CBE17-D11F-4D3F-A7FC-56BC8903C786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"373fae423eb2a1efeafbcd5b99e398bc451daee1","datavalue":{"value":"systolic architectures","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$C7C584BA-FDC0-4911-9C09-09238BABF3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q789180$54014A42-0F96-4D25-994C-9EB6ED8EEFBF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f2e7ec41e06c5aed18a2e9898ffd0bcb88881d20","datavalue":{"value":"Q113882252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$05B06A6D-41EA-4074-A23A-C8D3C058DEF2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7992c414b07bb0c7b8ce201afc40a3ead3f70780","datavalue":{"value":{"entity-type":"item","numeric-id":2529043,"id":"Q2529043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$3D0CDF65-1ACB-46E0-B1A2-E08CB4E34887","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":"Q789180$CF4C781D-6B2D-464A-A3D7-F7F5F21E96FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"21357c3bf4d2c0069a754fdd15d9c92011e4528f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90044-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q789180$23CBF584-02C6-4A51-8A8E-415408C376CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d3ad818919e168fe5712cca12b493c209dcf0da","datavalue":{"value":"W2069149028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789180$978DE6B1-D6DF-424F-AA1C-1117765BFDB7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9e735882f0114d9d1bd74d7bde93766d995370","datavalue":{"value":{"entity-type":"item","numeric-id":4065051,"id":"Q4065051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$4924D000-A773-4334-B37D-4AAFD9ABC4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77240d8edc9497a339f96af8fb98d73487d2ddc","datavalue":{"value":{"entity-type":"item","numeric-id":3875355,"id":"Q3875355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$428D937D-063A-4F97-A696-02E672D51C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e200b91b38dcda7a6afd8fe20171560b27754991","datavalue":{"value":{"entity-type":"item","numeric-id":3912011,"id":"Q3912011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$C27C65CA-9B2B-4170-A680-DC190EECB6A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95b43a6c4c4e31e641d94a071098874a458bb3af","datavalue":{"value":{"entity-type":"item","numeric-id":1151751,"id":"Q1151751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789180$EAF0DE4A-5DD9-4696-8EB5-657C23EC69F9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceafbd67ffdabda7cde4117bf98502cbf5913e45","datavalue":{"value":{"entity-type":"item","numeric-id":2945856,"id":"Q2945856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"def16d50709cbd62f4cf512d380c39048132c7a7","datavalue":{"value":{"amount":"+0.6947811841964722","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":"Q789180$6EFDFD6A-D3D2-4FED-8788-598E7F9CF5F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3324f8ceb38472cae454f11742a932f9a3b4d493","datavalue":{"value":{"entity-type":"item","numeric-id":3295750,"id":"Q3295750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5bb3bf014226467f3af62d05eeaf2e7c1afdcb8","datavalue":{"value":{"amount":"+0.6914374828338623","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":"Q789180$1ABA2F52-1F8B-4A22-B3C4-F4B10302D7CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73bdc7a45c77a16d00a42cf5a9ad7c6a193b6620","datavalue":{"value":{"entity-type":"item","numeric-id":1077163,"id":"Q1077163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fcf53778496f0106a8f7d8b311fccddbad7f42e","datavalue":{"value":{"amount":"+0.6886432766914368","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":"Q789180$DD2BB3EA-20B5-431D-B821-513494A848AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30e5f12d1e6d07eef34ecbf100de0b40d7c2158e","datavalue":{"value":{"entity-type":"item","numeric-id":2366720,"id":"Q2366720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5c8561bc3cfe584f59a77f7bb5245297ce3fa8a","datavalue":{"value":{"amount":"+0.6784252524375916","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":"Q789180$65B5209A-3925-4800-AD86-A8812BF87EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9bd16179492958bb3a9be2f340f97d244810c93","datavalue":{"value":{"entity-type":"item","numeric-id":4378033,"id":"Q4378033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b99a65c1d9fffc71626237499d80a69ece3d5daf","datavalue":{"value":{"amount":"+0.6777627468109131","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":"Q789180$02EC5B9D-58F2-40A5-9711-7C149B17E20B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Unbounded hardware is equivalent to deterministic Turing machines","badges":[]}}}}}