|
Mathematical logic, algebra and number theory
Generic Kleene fixed point theorem
A. N. Rybalovab a Omsk State University,
prospekt Mira 55A,
Omsk 644077, Russia
b Sobolev Institute of Mathematics,
Pevtsova str. 13,
Omsk 644043, Russia
Abstract:
Kleene's fixed point theorem states
that any algorithmic mapping $\mathcal{A}$ of the set of Turing machines
to the set of Turing machines
has a fixed point: there is a Turing machine $M$ such that
machine $\mathcal{A}(M)$ computes the same function as $M$.
In this paper we prove a generic analog of this theorem:
any algorithmic mapping $\mathcal{A}$ of a set
of “almost all” Turing machines
to the set of Turing machines has a fixed point.
Keywords:
Kleene fixed point theorem, generic computability.
Received April 26, 2017, published August 1, 2017
Citation:
A. N. Rybalov, “Generic Kleene fixed point theorem”, Sib. Èlektron. Mat. Izv., 14 (2017), 732–736
Linking options:
https://www.mathnet.ru/eng/semr819 https://www.mathnet.ru/eng/semr/v14/p732
|
Statistics & downloads: |
Abstract page: | 254 | Full-text PDF : | 54 | References: | 45 |
|