The scales of computability potentials: results and problems

A. G. Pinus ; S. V. Zhurkov

Fundamentalʹnaâ i prikladnaâ matematika, Tome 9 (2003) no. 3, pp. 145-164.

Résumé

We give a review of general known results on problems concerning the structure of scales of computability potentials of $n$-element algebras. We also formulate a number of natural open problems.

Bibliographie

[1] Zhurkov S. V., “O shkalakh potentsialov vychislimosti $n$-elementnykh unarov”, Vestnik NGU: matematika, mekhanika, informatika, 3:2 (2003), 20–31

[2] Zhurkov S. V., Pinus A. G., “Ob avtomorfizmakh shkal potentsialov vychislimosti $n$-elementnykh algebr”, Sib. mat. zhurn., 44:3 (2003), 606–621 | MR | Zbl

[3] Pinus A. G., “Ob uslovnykh termakh i tozhdestvakh na universalnykh algebrakh”, Vychislitelnye sistemy, 156, 1996, 59–78 | MR

[4] Pinus A. G., “Vnutrennie izomorfizmy i uslovno ratsionalnaya ekvivalentnost unaram i polyam”, Algebra i teoriya modelei, Izd-vo NGTU, Novosibirsk, 1997, 123–130

[5] Pinus A. G., “Ischislenie uslovnykh tozhdestv i uslovno ratsionalnaya ekvivalentnost”, Algebra i logika, 37:4 (1998), 432–459 | MR | Zbl

[6] Pinus A. G., “Ob uslovno ratsionalno ekvivalentnykh algebrakh”, Vychislitelnye sistemy, 165, 1999, 1–29

[7] Pinus A. G., “O funktsiyakh, kommutiruyuschikh s polugruppami preobrazovanii”, Sib. mat. zhurn., 41:6 (2000), 1409–1418 | MR | Zbl

[8] Pinus A. G., “Vnutrennie gomomorfizmy i pozitivno uslovnye termy”, Algebra i logika, 40:2 (2001), 158–173 | MR | Zbl

[9] Pinus A. G., “Programmno vychislimye funktsii na universalnykh algebrakh”, Matematicheskie voprosy kibernetiki, 10 (2001), 235–244

[10] Pinus A. G., “Uslovnye termy i ikh primenenie v algebre i teorii vychislenii”, Uspekhi mat. nauk, 56:4 (2001), 37–72 | MR

[11] Pinus A. G., “Slabye avtomorfizmy i zhirnost tochek shkal potentsialov vychislimosti”, Matematicheskie voprosy kibernetiki, 11 (2002), 15–26 | MR | Zbl

[12] Pinus A. G., Uslovnye termy i ikh primenenie v algebre i teorii vychislenii, Izd-vo NGTU, Novosibirsk, 2002

[13] Pinus A. G., “Shkaly potentsialov vychislimosti $n$-elementnykh algebr s ogranicheniyami na arnost” (to appear)

[14] Pinus A. G., “Porozhdennost konechnykh algebr, ikh uslovno ekvatsionalnye teorii i shkala potentsialov vychislimosti $n$-elementnykh algebr”, Algebra i teoriya modelei-4 (to appear)

[15] Pinus A. G., Zhurkov S. V., “Nekotorye zamechaniya o shkalakh potentsialov vychislimosti $n$-elementnykh algebr”, Algebra i teoriya modelei-3, Izd-vo NGTU, Novosibirsk, 2001, 107–113 | MR

[16] Pinus A. G., Zhurkov S. V., “O dlinakh shkal potentsialov vychislimosti $n$-elementnykh algebr”, Sib. mat. zhurn., 43:4 (2002), 858–863 | MR | Zbl

[17] Pinus A. G., Zhurkov S. V., “O shkalakh potentsialov vychislimosti universalnykh algebr”, Vychislitelnye sistemy, 169, 2002, 26–38 | MR | Zbl

[18] Yanov Yu. I., Muchnik A. A., “O suschestvovanii $k$-znachnykh zamknutykh klassov, ne imeyuschikh konechnogo bazisa”, DAN SSSR, 127:1 (1959), 144–146

[19] Glazek K., “Weak automorphisms in general algebra a short survey”, Algebra i teoriya modelei-3, Izd-vo NGTU, Novosibirsk, 2001, 26–31 | MR

[20] Jonsson B., Topics in universal algebra, Lect. Notes Math., 250, 1972 | MR | Zbl

[21] McKenzie R., “On algebraic version of categorical equivalence for varieties and more general algebraic categories”, Logic and Algebra, Marcel Dekker, New York, 1996, 211–243 | MR | Zbl

[22] Pinus A. G., “Conditional terms and its applications”, Algebraic Proceedings of the Kurosh Conference, Walter de Gruyter, Berlin, New York, 2000, 291–300 | MR

[23] Post E., “The two-valued iterative systems of mathematical logic”, Ann. of Math. Studies, 1941, no. 5 | MR | Zbl

[24] Stone M. G., “Subalgebra and automorphism structure in universal algebras; a concrete characterization”, Acta. Sci. Math., 1973 | MR