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. 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.E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, 1997. In Israel, Gurevich worked with Saharon Shelah on monadic second-order theories.Y. Gurevich. Monadic second-order theories. In J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, 1985, 479-506. The Forgetful Determinacy Theorem of Gurevich–Harrington is of that period as well.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.
From 1982 to 1998, Gurevich taught computer science at the University of Michigan, where he started to work on various aspects of computational complexity theoryY. Gurevich and S. Shelah. Expected computation time for Hamiltonian Path Problem. SIAM Journal on Computing 16:3, 1987, 486-502. including average case complexity.Y. Gurevich. Average case completeness. Journal of Computer and System Sciences 42:3, 1991, 346-398. He became one of the founders of the emerging field of finite model theory.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.
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.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 A few convincing axioms enabled derivation of the sequential ASM thesisY. Gurevich. Sequential Abstract State Machines capture sequential algorithms. ACM Transactions on Computational Logic 1(1), 2000. and the Church–Turing thesis.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. The ASM thesis has also been proven for some other classes of algorithms.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.
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, including access control,A. Blass, Y. Gurevich, M. Moskal, and I. Neeman. Evidential authorization. In S. Nanz (ed), The Future of Software Engineering, Springer 2011, 77–99. differential compression,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. and privacy.Y. Gurevich, E. Hudis, and J.M. Wing. Inverse privacy. Communications of the ACM 59(7), 2016, 38-42.
Since 1988, Gurevich has managed the column on Logic in Computer Science in the Bulletin of the European Association for Theoretical Computer Science. Since 2013 Gurevich has worked primarily on quantum computing,A. Bocharov, Y. Gurevich, and K.M. Svore. Efficient decomposition of single-qubit gates into V basis circuits. Physical Review A 88:1, 2013. while continuing research in his traditional areas.
Gurevich is a 2020 AAAS Fellow,AAAS Fellows, retrieved on Jan 11, 2021. a 1997 ACM Fellow,ACM Fellows, Association for Computing Machinery. Accessed February 16, 2010. a 1995 Guggenheim Fellow,Fellows List, John Simon Guggenheim Memorial Foundation. Accessed February 16, 2010. an inaugural fellow of the European Association for Theoretical Computer Science, a member of Academia Europaea, and Dr. Honoris Causa of Hasselt University in Belgium and of Ural State University in Russia.
References
External links Gurevich's Homepage Yuri Gurevich, Mathematics Genealogy Project