0103318 - UIVT-O 20040059 RIV NL eng J - Journal Article
Wiedermann, Jiří
Characterizing the Super-Turing Computing Power and Efficiency of Classical Fuzzy Turing Machines.
[Charakterizace super-turingovské výpočetní síly a efektivity klasického fuzzy turingova stroje.]
Theoretical Computer Science. Roč. 317, 1-3 (2004), s. 61-69. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA ČR GA201/02/1456
Institutional research plan: CEZ:AV0Z1030915
Keywords : fuzzy Turing machines * computability * computing power * computing effciency * Church-Turing thesis
Subject RIV: BA - General Mathematics
Impact factor: 0.676, year: 2004
DOI: https://doi.org/10.1016/j.tcs.2003.12.004

The first attempts concerning formalization of the notion of fuzzy algorithms in terms of Turing machines are dated in late 1960s when this notion was introduced by Zadeh. Recently, it has been observed that corresponding so-called classical fuzzy Turing machines can solve undecidable problems. In this paper we will give exact recursion-theoretical characterization of the computational power of this kind of fuzzy Turing machines.

První pokusy o formalizaci pojmu fuzzy algoritmů v termínech turingových strojů pocházejí z 80. let minulého století kdy byly příslušné pojmy zavedeny Zadehem. Nedávno bylo zjištěno, že odpovídající model tzv. klasického fuzzy turingova stroje může řešit nerozhodnutelné problémy. V článku podáme přesnou rekurzivně-teoretickou charakterizaci výpočetní síly tohoto typu turingových strojů.
Permanent Link: http://hdl.handle.net/11104/0010629