Zobrazeno 1 - 5
of 5
pro vyhledávání: '"Theory of computation ��� Turing machines"'
Publikováno v:
Logical Methods in Computer Science, 19(1), 15:1-15:32
The Turing machine models an old-fashioned computer, that does not interact with the user or with other computers, and only does batch processing. Therefore, we came up with a Reactive Turing Machine that does not have these shortcomings. In the Reac
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::79b53eb81e74c8e91989eaf1e3ecb22c
https://doi.org/10.46298/lmcs-19(1:15)2023
https://doi.org/10.46298/lmcs-19(1:15)2023
Autor:
Nakano, Keisuke
A function f is said to be idempotent if f(f(x)) = f(x) holds whenever f(x) is defined. This paper presents a computation model for idempotent functions, called an idempotent Turing machine. The computation model is necessarily and sufficiently expre
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eed21b344cb96e06cc2986c4d50214ee
Autor:
Komargodski, Ilan, Shi, Elaine
Oblivious RAM (ORAM) is a machinery that protects any RAM from leaking information about its secret input by observing only the access pattern. It is known that every ORAM must incur a logarithmic overhead compared to the non-oblivious RAM. In fact,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d3b9d059d2052031e5bf5b70630c5879
Autor:
Hoyrup, Mathieu
Publikováno v:
ICALP
ICALP, Jul 2020, Saarbrücken, Germany. ⟨10.4230/LIPIcs.ICALP.2020.132⟩
ICALP, Jul 2020, Saarbrücken, Germany. ⟨10.4230/LIPIcs.ICALP.2020.132⟩
International audience; This article is a study of descriptive complexity of subsets of represented spaces. Two competing measures of descriptive complexity are available. The first one is topological and measures how complex it is to obtain a set fr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b4acd8381a344d2bbdc7de82dd51dbb0
https://hal.inria.fr/hal-02483114/file/full.pdf
https://hal.inria.fr/hal-02483114/file/full.pdf
Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Celluar Automata and the 2-Handed Model of self-assembly both capable of universal computation. In
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5d05c9c2dee4fbe8745d434b073f0be0