Muchnik, Albert Abramovici
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită pe 25 mai 2021; verificările necesită
2 modificări .
Albert Abramovici Muchnik ( 2 ianuarie 1934 - 14 februarie 2019 ) a fost un matematician sovietic și rus care a lucrat în teoria computabilității și a logicii matematice .
Biografie
A studiat și și-a susținut teza pentru un candidat la științe fizice și matematice la Institutul Pedagogic de Stat din Moscova (supervizor - academician Pyotr Sergeevich Novikov ). Al. A. Muchnik și Richard Friedberg au rezolvat problema lui Post demonstrând în mod independent că există mulțimi enumerabile indecidabile la care problema opririi nu este reductibilă Turing și, în plus, există mulțimi reductibile non -Turing seturi enumerate. Metoda folosită în această demonstrație a fost numită metoda priorității și a devenit unul dintre instrumentele principale în teoria puterilor mulțimilor enumerabile, care a fost inițiată de Muchnik și Friedberg.
Al. A. Muchnik a definit conceptul de reducebilitate slabă pentru problemele de masă, continuând lucrările lui Yu. T. Medvedev, care a introdus conceptul de problemă de masă și a definit reducbilitatea puternică. Clasele de echivalență corespunzătoare în ceea ce privește reducția reciprocă formează o rețea , care este numită rețea Muchnik. Ea este o interpretare pentru logica intuiționistă .
Pe lângă teoria computabilității, Al. A. Muchnik a obținut rezultate în domeniul logicii cu mai multe valori (în colaborare cu Yu. I. Yanov), teoria automatelor și logica modală (cu soția sa, Nadezhda Mitrofanovna Ermolaeva)
elevul lui Al. A. Muchnik a fost Aleksey Lvovich Semyonov , supraveghetorul fiului său cel mare, Andrey Albertovich Muchnik (1958-2007)
Publicații
1956
- Indecidibilitatea problemei reductibilității în teoria algoritmilor, Doklady AN SSSR, 108(2), 194-197 (1956)
- Despre separabilitatea seturilor enumerabile recursiv, Doklady AN SSSR, 109(1), 29-32
1958
- Rezolvarea problemei de reductibilitate a lui Post și a altor probleme din teoria algoritmilor. I. Proceedings of the Moscow Mathematical Society, vol. 7, 391-405 (1958) Traducere: Amer. Matematică. soc. Transl. (2) 29 1963 197-215 [Raport dat la IMO la 16 octombrie 1956]
- Izomorfismul sistemelor de mulțimi enumerabile recursiv cu proprietăți efective. Proceedings of the Moscow Mathematical Society, vol. 7, 407-412 (1958)
[Se dovedește, în special, că perechile de mulțimi enumerabile efectiv inseparabile sunt izomorfe. Myhill scrie într-un rezumat la Math. Recenzii: Toate aceste rezultate și multe altele din aceeași zonă au fost descoperite de la lucrarea lui Mučnik (dar în necunoaștere) de R. Smullyan în teza sa de doctorat [Princeton, 1959; care urmează să fie publicată ca Teoria sistemelor formale în Annals of Mathematics Studies]. Deși este încurajator să vezi direcția comună a cercetării teoretice recursive în această țară și în Uniunea Sovietică, este trist că lipsa de comunicare între matematicienii celor două țări a dus – acum pentru a doua oară – la o dublare inutilă. de efort în acest domeniu]
1959
- A. A. Muchnik - R. Fridberg. Problema reductibilității mulțimilor enumerabile. Matematica, predarea ei, aplicații și istorie, Matematică. iluminare, ser. 2, 4, 1959, 233-236
[Expoziție populară]
- Yu. I. Yanov, AA Muchnik, Despre existența claselor închise cu valori k care nu au o bază finită. DAN URSS. 1959. V. 127. Nr. 1. S. 44-46.
1962
- A. A. Muchnik, S. G. Gindikin, Despre completitudinea unui sistem de elemente nesigure care implementează funcțiile algebrei logicii. Doklady AN SSSR, 144(5), 1007-1010 (1962)
[Când este posibil să se implementeze orice funcție în mod arbitrar fiabil, având elemente nesigure de unele tipuri și garantate altele fiabile]
1963
- Despre reductibilitatea puternică și slabă a problemelor algoritmice, Siberian Mathematical Journal, 4, 1328-1341 Computability, voi. 5, nr. 1, pp. 49-59, 2016
1965
- Despre reductibilitatea problemelor de rezoluție a seturilor enumerabile la probleme de separabilitate. Izv. Academia de Științe a URSS. Ser. Mat. 29:3 (1965), 717-724
[Problema rezoluției netriviale nu poate fi redusă la problema separabilității mulțimilor enumerabile; orice set enumerabil indecidabil poate fi împărțit în două părți inseparabile.]
- Gindikin, S.G.; Mučnik, AA Rezolvarea problemei completității pentru sistemele de funcții ale algebrei logicii cu realizare nesigură. (Engleză) Cybernet cu probleme. Nu. 15 1965 65-84.
1968
- Durata experimentului care determină structura unui automat finit puternic conectat. (Engleză) Cybernet cu probleme. Nu. 20 1968 159-171
1970
- Automatizare liniară generală. (Engleză) Cybernet cu probleme. Nu. 23 1970 171-208, 303-304.
1973
- A. A. Muchnik, A. N. Maslov, Evenimente liniare și probabiliste regulate, Tr. MIAN SSSR, 133 (1973), 149-168
1974
- Ermolaeva N. M., Muchnik A. A., Extensii modale ale calculilor logici de tip Hao Wang. Studii în limbaje formalizate și logici neclasice, M.: Nauka, 172-193.
1976
- Despre endomorfismele rețelelor distributive și logicii modal-temporale, Simpozionul al șaptelea All-Union privind logica și metodologia științei. Rezumate ale comunicării, Kiev: Naukova Dumka, 1976, 128-130.
- Ermolaeva NM, Muchnik AA, Logica modală definită prin endomorfisme ale rețelelor distributive. Studii în teoria mulțimilor și logica neoclasică, Moscova: Nauka, 229-246
1979
- Ermolaeva N. M., Muchnik A. A., Logica temporală pre-tabelă. Studii în logica neclasică și teoria mulțimilor, Moscova: Nauka, 288-297
- Ermolaeva NM, Muchnik AA, Extensii cu 4 valori închise funcțional ale algebrei booleene și logica corespunzătoare. Studii în logica neclasică și teoria mulțimilor, Moscova: Nauka, 298-315
1985
- Ermolaeva, NM; Muchnik, A.A. Expresibilitatea funcțională în unele logici modale tabulare. (engleză) Semiotică și știința informației, nr. 25, 94-119, 154, Akad. Nauk SSSR, Vsesoyuz. Inst. Ştiinţă. i Tehnologia. Inform., Moscova, 1985.
- Pe logica S5-TY, Keldysh Institute Preprint M. V. Keldysha, 2007, 086
Link -uri