On fixed points of rational transductions



: Vesa Halava, Tero Harju, Esa Sahla

Publisher: Elsevier

: 2018

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 732

: 85

: 88

: 4

: 0304-3975

: 1879-2294

DOI: https://doi.org/10.1016/j.tcs.2018.04.030


We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f : A* -> A* has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a corollary we obtain that the existence of a fixed point of injective computable functions is undecidable.



Last updated on 2024-26-11 at 20:45