A note on the diamond operator

Article type: Research Article

Authors: Westrick, Linda^{; *}

Affiliations: Department of Mathematics, The Pennsylvania State University, University Park, PA, USA. westrick@psu.edu

Correspondence: [*] Corresponding author. westrick@psu.edu.

Abstract: We show that if 1⩽WF and F⋆F⩽WF, then F◇⩽WF, where ⋆ and ◇ are the following operations in the Weihrauch lattice: ⋆ is the compositional product, which allows the use of two principles in sequence, while the diamond operator ◇ allows an arbitrary but finite number of uses of the given principle in sequence. This answers a question of Pauly.

Keywords: Compositional product, diamond operator, Weihrauch lattice, recursion theorem

DOI: 10.3233/COM-200295

Journal: Computability, vol. 10, no. 2, pp. 107-110, 2021