{"entities":{"Q2720332":{"pageid":2731071,"ns":120,"title":"Item:Q2720332","lastrevid":82826336,"modified":"2026-05-06T22:10:04Z","type":"item","id":"Q2720332","labels":{"en":{"language":"en","value":"Infinite time Turing machines with only one tape"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1610977"}},"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":"Q2720332$72B89707-84C6-41EC-8153-9BF37B7AE587","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c3f2710c5858612a13009a24593f27b8d7eb008","datavalue":{"value":"0990.03031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$793262B9-1639-42B1-9B79-3D0709FF9A55","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c237c0edc686c7e9971d10e201d8b8137b9a6f25","datavalue":{"value":{"entity-type":"item","numeric-id":167886,"id":"Q167886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720332$1C6EDF5B-77A4-4FCD-BE55-7E1456243F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cef267bc1b9ab6bb34391bb68e54c49ac7fc995e","datavalue":{"value":{"entity-type":"item","numeric-id":2720331,"id":"Q2720331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720332$5BB84CED-0931-43C5-976D-FCA5A7FB2385","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"491a46ed49ec5ab841ba9d0d08c465462a3e8c95","datavalue":{"value":{"time":"+2002-06-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2720332$E085F9BF-1ADE-49AB-A3B9-253298B430AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c13260eadcbe3f1af0a203e938838c435e9e0092","datavalue":{"value":"https://arxiv.org/abs/math/9907044","type":"string"},"datatype":"url"},"type":"statement","id":"Q2720332$CD1623BE-AD3E-4DB4-AB12-C2C27C248AE7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$C07EBE66-4D52-4F8A-9A91-455E7E1EE0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$BA8BC6D9-782F-4938-80C1-53C6B62E118D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"336909ab7d658bc708fbe71ee0cabf8b3a990e97","datavalue":{"value":"1610977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$80DA704B-464A-49AA-86FB-665DC0E4EE46","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7af9f92bf40c9e067f943b192611dd0a6b8b525","datavalue":{"value":"one-tape infinite Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720332$B3A637AE-21D7-4AFA-8815-E5AFA890A0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1337af1a3ca39d4a5f24b1093676a14a709efc29","datavalue":{"value":"supertask computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720332$53E053FF-AC67-4D85-9EC1-50E63039FC53","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":"Q2720332$4F99AA0D-FB2F-479C-A83C-7E607AD11A86","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a5266b086d57f02c870a2d9bcea855a418b287d3","datavalue":{"value":"W2015497757","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$9CE602B1-2409-4CAC-9D8D-2FE9E21F1CED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb988fce23a0359e7bd1fb593d0792aba81a368c","datavalue":{"value":{"entity-type":"item","numeric-id":2309496,"id":"Q2309496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d4fe1a9e10393bb3094212b2e9f73668856bab2","datavalue":{"value":{"amount":"+0.83597493","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$64FA61EF-1A70-48D0-B9C6-8C99D56E7687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba97f754b110d8c3e0d4b5f00359d4abb58f3f12","datavalue":{"value":{"entity-type":"item","numeric-id":4805392,"id":"Q4805392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a6f2ad2161afb941494a7713d0bf7d0811f69d4","datavalue":{"value":{"amount":"+0.82074326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$DF12862F-38A7-4EC7-8BAC-8D3B06D81983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d08cbdb04c87eef093dc1c7e9c4007d834dfc30","datavalue":{"value":{"entity-type":"item","numeric-id":5898830,"id":"Q5898830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9af44b49d6d4e0073da17ed0235458e5cff49bb1","datavalue":{"value":{"amount":"+0.81896424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$30398DCD-EC6D-4099-B720-44CCC8ECAD7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f97ac1193d59f1759f29d01ecbb7a247c47203a3","datavalue":{"value":{"entity-type":"item","numeric-id":1004086,"id":"Q1004086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d6272bd6f067aaae5434c40726cd829c7ccdfbc","datavalue":{"value":{"amount":"+0.8158536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$358E98F4-17C6-46C8-B050-DAB116961A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59f97e3abacd9c8c0970366a658a83970efe3937","datavalue":{"value":{"entity-type":"item","numeric-id":3507445,"id":"Q3507445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6635247e850a53c51441834fcd16f546a82c347","datavalue":{"value":{"amount":"+0.81317717","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$0101C4BE-9E7E-4674-B509-B090223A817E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cae8c888e72fa880e14438ee583d3fb1167e1ab7","datavalue":{"value":{"entity-type":"item","numeric-id":2011657,"id":"Q2011657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a964be5129890665bbc142c24c53ef649d26b717","datavalue":{"value":{"amount":"+0.8099105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$7DB4B5BD-1835-4E5C-8567-47DBCE47BFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"463eedefeb09043c5b8c5fa1edd9e83f341db03e","datavalue":{"value":{"entity-type":"item","numeric-id":3081648,"id":"Q3081648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07d5078e2961f7d4b18cb8d46b3d1dbe0f503ce1","datavalue":{"value":{"amount":"+0.8083362","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$20F696A6-83D3-4D1B-AED8-1C76BE80025F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aec94e4b1710737e21b4fadbccf227c363fb9fe3","datavalue":{"value":{"entity-type":"item","numeric-id":5326373,"id":"Q5326373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ee645ef7a139cc7afafb742f8549e61b147d22","datavalue":{"value":{"amount":"+0.8022335","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$F34B807F-278E-4696-82DC-D3F7C531FD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1472a0edd567e2410b76bf238c02e81136a4b131","datavalue":{"value":{"entity-type":"item","numeric-id":2267751,"id":"Q2267751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"606684b798d1cf2a3ef518461afaa1dcb5e78d41","datavalue":{"value":{"amount":"+0.79350376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$393DF7C3-ECEA-4CD5-9222-3A49E0459055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca517b2a3c837e9ed46f4d59a17df7078ed89872","datavalue":{"value":{"entity-type":"item","numeric-id":3608469,"id":"Q3608469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c443996ffc0d0a30f13e3d53a50926f58c0f14a3","datavalue":{"value":{"amount":"+0.78868556","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2720332$CF472EB9-4591-4D00-B2DA-ABFB53BC6FDA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ff8fd304e22c6f92a5960dd744431edd04669677","datavalue":{"value":"10.1002/1521-3870(200105)47:2%3C271::AID-MALQ271%3E3.0.CO;2-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2720332$9A41830C-8D1E-429D-BE05-DF6AF6EF4661","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fab74ebc66ce30b569117fa9db15c4cfa6993d4a","datavalue":{"value":{"text":"Infinite time Turing machines with only one tape","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2720332$249DFAB0-0319-4216-94DD-9C1972606C74","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"68cefe03c91c7bc1481d1ede29225e2a54af1e4c","datavalue":{"value":{"entity-type":"item","numeric-id":6561648,"id":"Q6561648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720332$89B6CB7D-F45C-481D-AFA4-31539C9D43B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e50ca0d1f9af3f443465bd8e1bcec97b72602162","datavalue":{"value":"In this paper the authors compare the computational powers of one-tape and multi-tape infinite time Turing machines. The infinite time Turing machines of three tapes (input/scratch/output) were introduced by the first author and \\textit{A. Lewis} [``Infinite time Turing machines'', J. Symb. Log. 65, 567-604 (2000; Zbl 0963.03064)]. An infinite time Turing machine is an ordinary Turing machine equipped with a new ``limit'' state. The authors point out that the machines with only one tape are in many respects as powerful as their multi-tape cousins. By simulating three-tape machines using one-tape machines, they show that the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for partial functions \\(f: R\\to N\\), the same class of computable functions. They also show that every ordinal that is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals. Nevertheless, the one-tape machines are not fully as powerful as multi-tape machines. An example of a computable function \\(f: R\\to R\\) which is not one-tape computable is presented. Yet the authors show that the closure under composition of the class of one-tape computable functions yields the full class of all infinite time computable functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2720332$771429FA-F1FF-4355-AE42-13D8571BC6AE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ca8ed344194345ca16bbb6704624120ee7ad077f","datavalue":{"value":{"entity-type":"item","numeric-id":589210,"id":"Q589210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2720332$400481FD-D7CD-4897-AF16-029C30AFF3EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Infinite time Turing machines with only one tape","badges":[]}}}}}