Boris (Boaz) Abramovich Trakhtenbrot (russian: Борис Авраамович Трахтенброт, he, בועז טרכטנברוט; 19 February 1921 – 19 September 2016) was a Russian-Israeli

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

theory of computation In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how algorithmic efficiency, efficiently they can be solved or t ...

, and

cybernetics Cybernetics is a wide-ranging field concerned with circular causality, such as feedback, in regulatory and purposive systems. Cybernetics is named after an example of circular causal feedback, that of steering a ship, where the helmsperson m ...

Biography

Trakhtenbrot was born in Brichevo, northern

Bessarabia Bessarabia (; Gagauz: ''Besarabiya''; Romanian: ''Basarabia''; Ukrainian: ''Бессара́бія'') is a historical region in Eastern Europe, bounded by the Dniester river on the east and the Prut river on the west. About two thirds of Be ...

(now Tîrnova,

Moldova Moldova ( , ; ), officially the Republic of Moldova ( ro, Republica Moldova), is a Landlocked country, landlocked country in Eastern Europe. It is bordered by Romania to the west and Ukraine to the north, east, and south. The List of states ...

). He studied at the Moldovan State Pedagogical Institute in Kishinev,

Chernivtsi University Chernivtsi National University (full name Yuriy Fedkovych Chernivtsi National University, uk, Чернівецький національний університет імені Юрія Федьковича) is a public university in the City o ...

, and the Ukrainian Academy of Science's Mathematical Institute, completing a Ph.D. at the latter institution in 1950. He worked at

Akademgorodok Akademgorodok ( rus, Академгородок, p=ɐkəˌdʲemɡərɐˈdok, "Academic Town") is a part of the Sovetsky District of the city of Novosibirsk, Russia, located south of the city center and about west of Koltsovo. It is the edu ...

Novosibirsk Novosibirsk (, also ; rus, Новосиби́рск, p=nəvəsʲɪˈbʲirsk, a=ru-Новосибирск.ogg) is the largest city and administrative centre of Novosibirsk Oblast and Siberian Federal District in Russia. As of the Russian Census ...

during the 1960s and 1970s. In 1964 Trakhtenbrot discovered and proved a fundamental result in

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

called the

gap theorem :''See also Gap theorem (disambiguation) for other gap theorems in mathematics.'' In computational complexity theory, the Gap Theorem, also known as the Borodin–Trakhtenbrot Gap Theorem, is a major theorem about the complexity of computable fun ...

. He also discovered and proved the theorem in

model theory In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...

, and

computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

now known as Trakhtenbrot's theorem. After immigrating to

Israel Israel (; he, יִשְׂרָאֵל, ; ar, إِسْرَائِيل, ), officially the State of Israel ( he, מְדִינַת יִשְׂרָאֵל, label=none, translit=Medīnat Yīsrāʾēl; ), is a country in Western Asia. It is situated ...

in 1981, he became a professor in the Faculty of

Exact Science The exact sciences, sometimes called the exact mathematical sciences, are those sciences "which admit of absolute precision in their results"; especially the mathematical sciences. Examples of the exact sciences are mathematics, optics, astron ...

s at

Tel Aviv University Tel Aviv University (TAU) ( he, אוּנִיבֶרְסִיטַת תֵּל אָבִיב, ''Universitat Tel Aviv'') is a public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Locate ...

, and continued as

professor emeritus ''Emeritus'' (; female: ''emerita'') is an adjective used to designate a retired chair, professor, pastor, bishop, pope, director, president, prime minister, rabbi, emperor, or other person who has been "permitted to retain as an honorary title ...

until his death. He died on 19 September 2016, at the age of 95.

Notes

External links

* * * 1921 births 2016 deaths Bessarabian Jews Israeli computer scientists Israeli Jews 20th-century Israeli mathematicians Israeli people of Moldovan-Jewish descent Moldovan computer scientists Moldovan Jews 20th-century Moldovan mathematicians People from Dondușeni District Soviet computer scientists Soviet emigrants to Israel Soviet mathematicians Academic staff of Tel Aviv University {{Russia-mathematician-stub