| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875481 | Theoretical Computer Science | 2018 | 7 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Vesa Halava, Tero Harju, Esa Sahla,