Yuri Gurevich , profesor emérito en la Universidad de Michigan , es un americano científico informático y matemático e inventor de máquinas de estados abstractos .
Gurevich nació y se educó en la Unión Soviética . Enseñó matemáticas allí y luego en Israel antes de mudarse a los Estados Unidos en 1982. El trabajo más conocido de su período soviético es el clásico problema de decisión . [1] En Israel, Gurevich trabajó con Saharon Shelah en teorías monádicas de segundo orden . [2] El teorema de la determinación olvidadiza de Gurevich- Harrington también pertenece a ese período. [3]
De 1982 a 1998, Gurevich enseñó informática en la Universidad de Michigan , donde comenzó a trabajar en varios aspectos de la teoría de la complejidad computacional [4], incluida la complejidad promedio de los casos. [5] Se convirtió en uno de los fundadores del campo emergente de la teoría de modelos finitos . [6]
Lo más importante es que se interesó por el problema de qué es un algoritmo . Esto lo llevó a la teoría de las máquinas de estado abstractas (ASM). La Tesis de ASM dice que, en términos de comportamiento, cada algoritmo es un ASM. [7] Unos pocos axiomas convincentes permitieron derivar la tesis secuencial de la ASM [8] y la tesis de Church-Turing. [9] La tesis ASM también ha sido probada para algunas otras clases de algoritmos. [10] [11]
De 1998 a 2018, Gurevich estuvo en Microsoft Research, donde fundó un grupo sobre Fundamentos de la Ingeniería de Software. El grupo construyó Spec Explorer basado en la teoría de las máquinas de estado abstractas. La herramienta fue adoptada por el equipo de Windows ; una versión modificada de la herramienta ayudó a Microsoft a satisfacer las demandas de la Unión Europea de especificaciones ejecutables de alto nivel. Más tarde, Gurevich trabajó con diferentes grupos de Microsoft en varios temas de eficiencia, seguridad y protección, [12] incluyendo control de acceso, [13] compresión diferencial [14] y privacidad. [15]
Desde 1988, Gurevich ha dirigido la columna sobre Lógica en Ciencias de la Computación en el Boletín de la Asociación Europea de Ciencias de la Computación Teórica. [16] Desde 2013, Gurevich ha trabajado principalmente en computación cuántica , [17] mientras continuaba investigando en sus áreas tradicionales.
Gurevich es miembro de la AAAS 2020 , [18] miembro de la ACM de 1997 , [19] miembro del Guggenheim de 1995 , [20] miembro inaugural de la Asociación Europea de Ciencias de la Computación Teórica , [21] miembro de la Academia Europaea y el Dr. Honoris Causa de la Universidad Hasselt en Bélgica y de la Universidad Estatal de los Urales en Rusia .
Referencias
- ^ E. Börger, E. Grädel e Y. Gurevich. El problema clásico de la decisión. Springer, 1997.
- ^ Y. Gurevich. Teorías monádicas de segundo orden. En J. Barwise y S. Feferman (eds.), Model-Theoretic Logics, Springer, 1985, 479-506.
- ^ Y. Gurevich y L. Harrington. Autómatas, árboles y juegos. STOC '82: Actas del decimocuarto simposio anual de ACM sobre teoría de la computación, 1982, 60-65.
- ^ Y. Gurevich y S. Shelah. Tiempo de cálculo esperado para el problema de la trayectoria hamiltoniana. SIAM Journal on Computing 16: 3, 1987, 486-502.
- ^ Y. Gurevich. Completitud promedio de casos. Journal of Computer and System Sciences 42: 3, 1991, 346-398.
- ^ Y. Gurevich. Hacia una lógica adaptada a la complejidad computacional. En M Richter et al. (eds.), Computación y teoría de la prueba. Springer Lecture Notes in Mathematics 1104, 1984, 175-216.
- ^ Y. Gurevich. Evolving Algebra 1993: Lipari Guide. En E. Börger (ed.), Specification and Validation Methods, Oxford University Press, 1995, 9–36. https://arxiv.org/abs/1808.06255
- ^ Y. Gurevich. Las máquinas de estado abstracto secuencial capturan algoritmos secuenciales. Transacciones ACM en lógica computacional 1 (1), 2000.
- ^ N. Dershowitz e Y. Gurevich. Una axiomatización natural de la computabilidad y prueba de la tesis de Church. Boletín de lógica simbólica 14: 3, 2008, 299-350.
- ^ A. Blass e Y. Gurevich. Las máquinas de estado abstracto capturan algoritmos paralelos. ACM Transactions on Computational Logic 4 (4), 2003, 578–651 y 9 (3), 2008, artículo 19.
- ^ A. Blass, Y. Gurevich, D. Rosenzweig y B. Rossman . Algoritmos interactivos de pequeño paso II: Máquinas de estados abstractos y el teorema de caracterización. Métodos lógicos en informática 3 (4), 2007, artículo 4.
- ^ https://patents.google.com/?inventor=yuri+gurevich
- ^ A. Blass, Y. Gurevich, M. Moskal e I. Neeman. Autorización probatoria. En S. Nanz (ed), The Future of Software Engineering, Springer 2011, 77–99.
- ^ N. Bjørner, A. Blass e Y. Gurevich. Fragmentación dependiente del contenido para compresión diferencial: el enfoque máximo local. Revista de ciencia de sistemas informáticos 76 (3-4), 2010, 154-203.
- ^ Y. Gurevich, E. Hudis y JM Wing. Privacidad inversa. Comunicaciones de la ACM 59 (7), 2016, 38-42.
- ^ https://eatcs.org/index.php/eatcs-bulletin
- ^ A. Bocharov, Y. Gurevich y KM Svore. Descomposición eficiente de puertas de un solo qubit en circuitos de base V. Revisión física A 88: 1, 2013.
- ^ AAAS Fellows , recuperado el 11 de enero de 2021.
- ^ Becarios de ACM , Asociación de maquinaria informática . Consultado el 16 de febrero de 2010.
- ^ Lista de becarios , archivada el 22 de junio de 2011 en la Wayback Machine John Simon Guggenheim Memorial Foundation . Consultado el 16 de febrero de 2010.
- ^ "EATCS nombra becarios de 2014", Hitos: Premios de Ciencias de la Computación, Nombramientos, Comunicaciones de la ACM , 58 (1): 24 de enero de 2015, doi : 10.1145 / 2686734 , S2CID 11485095
enlaces externos
- Página de inicio de Gurevich
- Yuri Gurevich , Proyecto de genealogía matemática