TY - GEN

T1 - Idempotent Turing Machines

AU - Nakano, Keisuke

N1 - Funding Information:
by JSPS KAKENHI Grant
Publisher Copyright:
© Keisuke Nakano; licensed under Creative Commons License CC-BY 4.0 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021).

PY - 2021/8/1

Y1 - 2021/8/1

N2 - 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 expressive in the sense that not only does it always compute an idempotent function but also every idempotent computable function can be computed by an idempotent Turing machine. Furthermore, a few typical properties of the computation model such as robustness and universality are shown. Our computation model is expected to be a basis of special-purpose (or domain-specific) programming languages in which only but all idempotent computable functions can be defined.

AB - 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 expressive in the sense that not only does it always compute an idempotent function but also every idempotent computable function can be computed by an idempotent Turing machine. Furthermore, a few typical properties of the computation model such as robustness and universality are shown. Our computation model is expected to be a basis of special-purpose (or domain-specific) programming languages in which only but all idempotent computable functions can be defined.

KW - Computable functions

KW - Computation model

KW - Idempotent functions

KW - Turing machines

UR - http://www.scopus.com/inward/record.url?scp=85115365119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115365119&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2021.79

DO - 10.4230/LIPIcs.MFCS.2021.79

M3 - Conference contribution

AN - SCOPUS:85115365119

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

A2 - Bonchi, Filippo

A2 - Puglisi, Simon J.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021

Y2 - 23 August 2021 through 27 August 2021

ER -