This article uses bare URLs, which are uninformative and vulnerable to link rot. Please consider converting them to full citations to ensure the article remains verifiable and maintains a consistent citation style. Several templates and tools are available to assist in formatting, such as reFill (documentation) and Citation bot (documentation).(September 2022) (Learn how and when to remove this message)
Yuri Gurevich, Professor Emeritus at the University of Michigan, is an American computer scientist and mathematician and the inventor of abstract state machines.
Gurevich was born and educated in the Soviet Union.[1] He taught mathematics there and then in Israel before moving to the United States in 1982.
The best-known work of his Soviet period is on the classical decision problem.[2]
In Israel, Gurevich worked with Saharon Shelah on
monadic second-order theories.[3]
The Forgetful Determinacy Theorem of Gurevich–Harrington is of that period as well.[4]
From 1982 to 1998, Gurevich taught computer science at the University of Michigan, where he started to work on various aspects of computational complexity theory[5]
including average case complexity.[6]
He became one of the founders of the emerging field of finite model theory.[7]
Most importantly, he became interested in the problem of what an algorithm is. This led him to the theory of abstract state machines (ASMs). The ASM Thesis says that, behaviorally, every algorithm is an ASM.[8]
A few convincing axioms enabled derivation of the sequential ASM thesis[9]
and the Church–Turing thesis.[10]
The ASM thesis has also been proven for some other classes of algorithms.[11][12]
From 1998 to 2018, Gurevich was with Microsoft Research where he founded a group on Foundations of Software Engineering. The group built Spec Explorer based on the theory of abstract state machines. The tool was adopted by the Windows team; a modified version of the tool helped Microsoft meet the European Union demands for high-level executable specifications. Later, Gurevich worked with different Microsoft groups on various efficiency, safety, and security issues,[13]
including access control,[14]
differential compression,[15]
and privacy.[16]
Since 1988, Gurevich has managed the column on Logic in Computer Science in the Bulletin of the European Association for Theoretical Computer Science.[17]
Since 2013 Gurevich has worked primarily on
quantum computing,[18]
while continuing research in his traditional areas.
Gurevich is a 2020 AAAS Fellow,[19]
a 1997 ACM Fellow,[20]
a 1995 Guggenheim Fellow,[21]
an inaugural fellow of the European Association for Theoretical Computer Science,[22]
a member of Academia Europaea, and Dr. Honoris Causa of Hasselt University in Belgium and of Ural State University in Russia.
^Blass, Andreas; Dershowitz, Nachum; Reisig, Wolfgang (2010), Blass, Andreas; Dershowitz, Nachum; Reisig, Wolfgang (eds.), "Yuri, Logic, and Computer Science", Fields of Logic and Computation, Lecture Notes in Computer Science, vol. 6300, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 1–48, doi:10.1007/978-3-642-15025-8_1, ISBN 978-3-642-15024-1, retrieved 2023-07-05
^E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, 1997.
^Y. Gurevich. Monadic second-order theories. In J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, 1985, 479-506.
^Y. Gurevich and L. Harrington. Automata, Trees, and Games. STOC '82: Proceedings of the Fourteenth annual ACM Symposium on Theory of Computing, 1982, 60-65.
^Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian Path Problem. SIAM Journal on Computing 16:3, 1987, 486-502.
^Y. Gurevich. Average case completeness. Journal of Computer and System Sciences 42:3, 1991, 346-398.
^Y. Gurevich. Toward logic tailored for computational complexity. In M Richter et al. (eds.), Computation and Proof Theory. Springer Lecture Notes in Mathematics 1104, 1984, 175-216.
^Y. Gurevich. Evolving Algebra 1993: Lipari Guide. In E. Börger (ed.), Specification and Validation Methods, Oxford University Press, 1995, 9–36. https://arxiv.org/abs/1808.06255
^Y. Gurevich. Sequential Abstract State Machines capture sequential algorithms. ACM Transactions on Computational Logic 1(1), 2000.
^N. Dershowitz and Y. Gurevich. A natural axiomatization of computability and proof of Church’s Thesis. Bulletin of Symbolic Logic 14:3, 2008, 299-350.
^A. Blass and Y. Gurevich. Abstract State Machines Capture Parallel Algorithms. ACM Transactions on Computational Logic 4(4), 2003, 578–651, and 9(3), 2008, article 19.
^A. Blass, Y. Gurevich, D. Rosenzweig, and B. Rossman. Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem. Logical Methods in Computer Science 3(4), 2007, paper 4.
^"Google Patents".
^A. Blass, Y. Gurevich, M. Moskal, and I. Neeman. Evidential authorization. In S. Nanz (ed), The Future of Software Engineering, Springer 2011, 77–99.
^N. Bjørner, A. Blass, and Y. Gurevich. Content-dependent chunking for differential compression: The local maximum approach. Journal of Computer Systems Science 76(3-4), 2010, 154-203.
^Y. Gurevich, E. Hudis, and J.M. Wing. Inverse privacy. Communications of the ACM 59(7), 2016, 38-42.
^https://eatcs.org/index.php/eatcs-bulletin
^A. Bocharov, Y. Gurevich, and K.M. Svore. Efficient decomposition of single-qubit gates into V basis circuits. Physical Review A 88:1, 2013.
^AAAS Fellows, retrieved on Jan 11, 2021.
^ACM Fellows, Association for Computing Machinery. Accessed February 16, 2010.
^Fellows List, Archived June 22, 2011, at the Wayback Machine John Simon Guggenheim Memorial Foundation. Accessed February 16, 2010.
^"EATCS names 2014 fellows", Milestones: Computer Science Awards, Appointments, Communications of the ACM, 58 (1): 24, January 2015, doi:10.1145/2686734, S2CID 11485095
YuriGurevich, Professor Emeritus at the University of Michigan, is an American computer scientist and mathematician and the inventor of abstract state...
structure to the category of algorithms. cf [164] Andreas Blass and YuriGurevich "Algorithms: A Quest for Absolute Definitions" Bulletin of the European...
Yuri Alekseyevich Gagarin (9 March 1934 – 27 March 1968) was a Soviet pilot and cosmonaut who, aboard the first successful crewed spaceflight, became the...
machines" Gurevich references: John E. Savage (1998), Models of Computation: Exploring the Power of Computing. Addison Wesley Longman. YuriGurevich (1988)...
original on 18 December 2018. Retrieved 4 September 2021. Vasilev, Yuri. Gurevich, Vladimir; Gaydamak, Arcadi; Sokolov, Sergey Viktorovich; Bogomolov...
ISBN 0-444-88071-2 (Volume A). QA76.H279 1990. Nachum Dershowitz; YuriGurevich (September 2008). "A natural axiomatization of computability and proof...
McGraw–Hill Book Company, New York. ISBN 0-07-004357-4. Blass, Andreas; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions" (PDF). Bulletin...
experimentation, testing model executions). The concept of ASMs is due to YuriGurevich, who first proposed it in the mid-1980s as a way of improving on Turing's...
Matzinger Cees Dekker Kathleen Eisenhardt Frank De Winne Tom Jovin YuriGurevich David Montgomery Michael Berridge Harold Kroto Roger Langenaken David...
Verification", Fields of Logic and Computation II: Essays Dedicated to YuriGurevich on the Occasion of His 75th Birthday, Lecture Notes in Computer Science...
computability logic, Dina Q. Goldin's Persistent Turing Machines (PTMs), and YuriGurevich's abstract state machines. Peter Wegner has additionally done a great...
Edelsbrunner 2014 Zoltán Ésik 2016 Mike Fellows 2014 Fedor Fomin 2019 YuriGurevich 2014 Mohammad Hajiaghayi 2020 Magnús M. Halldórsson 2020 David Harel...
Oblast. He tested several supersonic fighter aircraft Mikoyan-Gurevich MiG-21, Mikoyan-Gurevich MiG-23, Mikoyan MiG-29 and their modifications, and participated...
of Ekaterinburg Gennady Burbulis, the Russian politician and scholar YuriGurevich, the computer scientist Michael Zinigrad, the Israeli scientist Gleb...
Science & Technology Patricia M. Graney Creative Arts Choreography YuriGurevich Computer Science Peter Haidu Humanities Medieval Literature Gwendolyn...
Davis David P. Dobkin Herbert Freeman Hector Garcia-Molina Irene Greif YuriGurevich John L. Hennessy Zvi Kedem Richard A. Kemmerer H. W. Lawson Der-Tsai...
Richard Soley, Igor Agamirzian, Grady Booch, Lars Bak, Alexander L. Wolf, YuriGurevich, Victor Ivannikov, Stephen Mellor, Larry Constantine, Ivar Jacobson...
Intertoto Cup 1997 with FC Dynamo Moscow: 1 game. Yuri Tishkov at FootballFacts.ru (in Russian) Gurevich, Pavel (11 January 2018). "Мама Тишкова: "Потеряла...
Testing 2008, LNCS 4949, Springer, 2008, pp. 39-76. Wolfgang Grieskamp, YuriGurevich, Wolfram Schulte, and Margus Veanes. Generating finite state machines...
October 2010). Fields of Logic and Computation: Essays Dedicated to YuriGurevich on the Occasion of His 70th Birthday. Springer. p. 468. ISBN 978-3-642-15024-1...
Feinberg 1977: Yakov Zeldovich and Fyodor Shapiro [ru] 1980: Isai Izrailevich Gurevich and Boris Nikolsky 1981: William d'Haeseleer 1983: Vladimir Mostovoy 1986:...