Yuri Gurevich

Yuri Gurevich, Professor Emeritus at the University of Michigan, is an American computer scientist and mathematician and the inventor of abstract state machines.

Yuri Gurevich at ETH Zurich in May 2004, photograph by Bertrand Meyer.

Gurevich was born and educated in the Soviet Union. 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.^[1] In Israel, Gurevich worked with Saharon Shelah on monadic second-order theories.^[2] The Forgetful Determinacy Theorem of Gurevich–Harrington is of that period as well.^[3]

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^[4] including average case complexity.^[5] He became one of the founders of the emerging field of finite model theory.^[6]

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.^[7] A few convincing axioms enabled derivation of the sequential ASM thesis^[8] and the Church–Turing thesis.^[9] The ASM thesis has also been proven for some other classes of algorithms.^[10][11]

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,^[12] including access control,^[13] differential compression,^[14] and privacy.^[15]

Since 1988, Gurevich has managed the column on Logic in Computer Science in the Bulletin of the European Association for Theoretical Computer Science.^[16] Since 2013 Gurevich has worked primarily on quantum computing,^[17] while continuing research in his traditional areas.

Gurevich is a 2020 AAAS Fellow,^[18] a 1997 ACM Fellow,^[19] a 1995 Guggenheim Fellow,^[20] an inaugural fellow of the European Association for Theoretical Computer Science,^[21] a member of Academia Europaea, and Dr. Honoris Causa of Hasselt University in Belgium and of Ural State University in Russia.

References

1. E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, 1997.
2. Y. Gurevich. Monadic second-order theories. In J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, 1985, 479-506.
3. 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.
4. Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian Path Problem. SIAM Journal on Computing 16:3, 1987, 486-502.
5. Y. Gurevich. Average case completeness. Journal of Computer and System Sciences 42:3, 1991, 346-398.
6. 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.
7. 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
8. Y. Gurevich. Sequential Abstract State Machines capture sequential algorithms. ACM Transactions on Computational Logic 1(1), 2000.
9. 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.
10. 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.
11. 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.
12. "Google Patents".
13. A. Blass, Y. Gurevich, M. Moskal, and I. Neeman. Evidential authorization. In S. Nanz (ed), The Future of Software Engineering, Springer 2011, 77–99.
14. 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.
15. Y. Gurevich, E. Hudis, and J.M. Wing. Inverse privacy. Communications of the ACM 59(7), 2016, 38-42.
16. https://eatcs.org/index.php/eatcs-bulletin
17. A. Bocharov, Y. Gurevich, and K.M. Svore. Efficient decomposition of single-qubit gates into V basis circuits. Physical Review A 88:1, 2013.
18. AAAS Fellows, retrieved on Jan 11, 2021.
19. ACM Fellows, Association for Computing Machinery. Accessed February 16, 2010.
20. Fellows List, June 22, 2011, at the Wayback Machine John Simon Guggenheim Memorial Foundation. Accessed February 16, 2010.
21. "EATCS names 2014 fellows", Milestones: Computer Science Awards, Appointments, Communications of the ACM, 58 (1): 24, January 2015, doi:10.1145/2686734, S2CID 11485095

External links

• Gurevich's Homepage
• Yuri Gurevich, Mathematics Genealogy Project

 

Wikimedia Commons has media related to Yuri Gurevich.