{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T14:21:34Z","timestamp":1777645294009,"version":"3.51.4"},"reference-count":0,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p>Querying its own history is an important mechanism in the\n\t\t\t computations, especially those interacting with people or other computations\n\t\t\t such as transaction processing, electronic data interchange. John McCarthy in\n\t\t\t his Elephant programming language proposal suggested exploiting the referring\n\t\t\t to the past as the main programming primitive. In this paper we study the\n\t\t\t computational power of such primitive. In order to do that we propose a refined\n\t\t\t formal model, History Dependent Machine (HDM), which uses querying the history\n\t\t\t as its sole computational primitive. Our main result may be spelled in general\n\t\t\t terms as: a model with a single agent wandering around a pool of resources and\n\t\t\t having ability to check its own history for simple temporal properties has a\n\t\t\t universal computational power. Moreover, HDM can simulate any multicounter\n\t\t\t machine in real time. Then we show that the computations of HDM may be\n\t\t\t specified in the extension of propositional linear temporal logic by flexible\n\t\t\t constants, the abstraction operator and equality. We use then universality of\n\t\t\t HDM model to show that the above extension with a single flexible constant is\n\t\t\t not recursively axiomatizable.<\/jats:p>","DOI":"10.3233\/fi-2009-0049","type":"journal-article","created":{"date-parts":[[2019,12,2]],"date-time":"2019-12-02T22:33:35Z","timestamp":1575326015000},"page":"395-409","source":"Crossref","is-referenced-by-count":3,"title":["On the Computational Power of Querying the History"],"prefix":"10.1177","volume":"91","author":[{"given":"Alexei","family":"Lisitsa","sequence":"first","affiliation":[{"name":"Computer Science Department, University of Liverpool,\r\t\t\t Ashton Building, Ashton Street, Liverpool, L69 3BX, UK. Lisitsa@liverpool.ac.uk;\r\t\t\t Potapov@liverpool.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Potapov","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Liverpool,\r\t\t\t Ashton Building, Ashton Street, Liverpool, L69 3BX, UK. Lisitsa@liverpool.ac.uk;\r\t\t\t Potapov@liverpool.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2009,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2009-0049","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2009-0049","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T06:31:53Z","timestamp":1777444313000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2009-0049"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.3233\/FI-2009-0049"],"URL":"https:\/\/doi.org\/10.3233\/fi-2009-0049","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"value":"0169-2968","type":"print"},{"value":"1875-8681","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}