Трахтенброт, Борис Авраамович

Борис Авраамович Трахтенброт
Учёная степень:	доктор физико-математических наук
Учёное звание:	профессор

Борис Авраамович Трахтенброт (также Борис Абрамович, англ. Boris (Boaz) Trachtenbrot, Trakhtenbrot, Trajtenbrot & Trahtenbrot, ивр. ‏בועז טרכטנברוט‏‎; 20 февраля 1921, Бричево Сорокского уезда, Бессарабия — 19 сентября 2016, Реховот, Израиль) — советский и израильский математик в области математической логики, теории алгоритмов и кибернетики. Доктор физико-математических наук (1962), профессор (1963).

Один из начинателей теоретической информатики в СССР, видный теоретик в области дискретной математики и формальных языков, а также математической логики, электронных вычислительных машин, в особенности теории автоматов (см. теорему неразрешимости Трахтенброта и Щелевую теорему Трахтенброта—Бородина).

Биография

Борис Трахтенброт (первоначально Трахтенбройт) родился в бессарабской еврейской земледельческой колонии Бричево (ныне Дондюшанского района Молдавии) в 1921 году в семье Абрама Трахтенбройта, в 1941 году высланного на поселение и принудительные работы в Сибирь. Учился в начальной школе в Бричево, потом в Бельцах и в мужской гимназии в Сороках (окончил последнюю в 1939 году).

В 1940 году поступил на физико-математическое отделение Кишинёвского педагогического института. В начале июля 1941 года Б. А. Трахтенброту удалось бежать из осаждённого города и попасть в Чкалов, где он продолжил обучение в местном педагогическом институте, а через год перевёлся обратно в эвакуированный в Бугуруслан Кишинёвский педагогический институт. Одновременно работал на обувной фабрике, затем на строительстве газовой магистрали между Бугурусланом и Куйбышевом. В августе 1944 года вместе с педагогическим институтом вернулся в Кишинёв. Получив диплом об окончании института в 1945 году работал учителем в Бельцах. Приняв решение серьёзно заняться математикой, в том же году поступил на физико-математический факультет в Черновицкий университет, где слушал лекции по теории вероятностей Александра Боброва. В 1947 году окончил математический факультет Черновицкого университета и поступил в аспирантуру в Институт математики Академии наук Украинской ССР в Киеве. Специализировался в математической логике под руководством П. С. Новикова, защитил диссертацию в 1950 году.

В 1950—1958 годах работал в Пензенском педагогическом институте, в 1958—1960 годах — в Пензенском политехническом институте. С 1960 года — в Институте математики Сибирского отделения Академии Наук СССР (Новосибирский Академгородок) и в Новосибирском государственном университете (с 1963 года — профессор, заведующий отделом).

После переезда в Израиль в декабре 1980 года — профессор отделения точных и компьютерных наук Тель-Авивского университета (с 1991 года — professor emeritus). Член редколлегии журнала [www.elsevier.com/wps/find/journaleditorialboard.cws_home/622844/editorialboard?navopenmenu=-2 «Information and Computation»] (Elsevier).

Публиковаться начал в 1950 году (представлена и доказана теорема неразрешимости Трахтенброта) и тогда же защитил кандидатскую диссертацию в Институте математики Украинской Академии Наук (Киев) по теме «Разрешимость проблем для конечных классов и определения конечных классов» под научным руководством профессора (впоследствии академика) П. С. Новикова. Первая же монография математика («Алгоритмы и машинное решение задач», в 2-х изданиях — 1957 и 1960) была переведена на болгарский, английский, французский (оба издания), чешский, японский (оба издания), испанский (оба издания), итальянский, турецкий, немецкий и польский языки. Монографии «Введение в теорию конечных автоматов» (1962), «Конечные автоматы: поведение и синтез» (1970) и «Алгоритмы и вычислительные автоматы» (1974) также были переведены на несколько иностранных языков.

В 2008 году в серии «Столпы компьютерных наук» (Pillars of Computer Science) издательства Springer Verlag вышел сборник научных статей в честь 85-летия Б. А. Трахтенброта. Среди учеников и соавторов Б. А. Трахтенброта — Янис Барздинь (р. 1937).

Семья

• Жена (с 1946) — Белла (Берта) Рабинович (1921, Атаки — 2013, Реховот).
  • Сын — Марк Борисович Трахтенброт (род. 1950), математик в области формальных методов спецификации и тестирования сложных систем, сотрудник Отдела программирования ВЦ СО АН (1971—1984), учёный секретарь Научного совета Вычислительного Центра Сибирского отделения АН СССР в Новосибирске ([www.hit.ac.il/staff/scie/ma_t/ личная страница]), ныне заведующий отделом компьютерных наук в Холонском институте технологии (Израиль).
  • Сын — Иосиф Борисович Трахтенброт (род. 1952), экономист.

Также

• Trakhtenbrot’s theorem (1950)
• Gap theorem (1964)

Библиография

См. частичную библиографию [web.archive.org/web/20110927072358/www.cs.tau.ac.il/~nachum/BoazPub.pdf здесь] (недоступная ссылка с 13-05-2013 (4002 дня) — история).

Монографии

• Алгоритмы и машинное решение задач. В серии «Популярные лекции по математике». Гостехиздат: Москва, 1957 (издание на японском языке — Токио, 1959 и 1964).
• Wieso können Automaten Rechnen (на немецком языке). Deutsche Verlag der Wissenschaften: Берлин, 1959.

• Алгоритмы и машинное решение задач. Второе (расширенное) издание. Физматгиз: Москва, 1960.
• Algoritmy i automatyczne rozwiazyvanie zadan (на польском языке). Pasttwowe Wydawnictwo Naukowe: Варшава, 1961.
• Algorithmes et machines à calculer (на французском языке). Dunod: Париж, 1963.
• Algoritmy a strojove reseni ulokh (на чешском языке). Nakladatelstvi Ceskoslovenske akademie ved: Прага, 1963.
• Алгоритми и машинно решаване на задачи (на болгарском языке). Държавно издателство Техника: София, 1963.
• Algorithms and Automatic Computing Machines (на английском языке). В серии «Topics in Mathematics». D.C. Heath and Company: Бостон, 1963.
• Algoritmi e Macchine Calcolatrici Automatiche (на итальянском языке). Progresso Tecnico Editoriale: Милан, 1964.
• Algoritmalar ve Otomatik Hesap Makinalari (на турецком языке). Turk Matematik Dernegi Yaynlari: Стамбул, 1964.
• Introduccion a la Teoria Matematica de las Computadoras y de la Programacion (на испанском языке). Siglo Veintiuno Editores SA: Мехико, 1967.
• Algorithme et Resolution de Problemes par des Machines (на французском языке). Вторая часть книги Nouvelles Orientations des Mathematiques (И. Яглом, Б. Трахтенброт, Г. Венцель, А. Солодовников). Editions Mir: Москва, 1975.
• Los Algoritmos y la Resolución Automática de Problemas (на испанском языке). Editorial Mir: Москва, 1977.
• アルゴリズムの数学 (単行本（ソフトカバー）) (на японском языке, см. [books.cliptrash.com/b-108219/ здесь] (недоступная ссылка с 13-05-2013 (4002 дня))). 東京図書: Токио, 1994.

• Введение в теорию конечных автоматов (совместно с Н. Е. Кобринским). Физматгиз (Государственное издательство физико-математической литературы): Москва, 1962.

• Introduction to the Theory of Finite Automata (на английском языке). В серии «Studies in Logic and the Foundations of Mathematics». North-Holland Publishing Company: Амстердам, 1965.
• Uvod do Teorie Konecnych Automatu (на чешском языке). Nakladatelstvi Technicke Literatury: Прага, 1967.
• Einfuhrung in die Theory Endlicher Automaten (на немецком языке). Akademie-Verlag: Берлин, 1967.

• Сложность алгоритмов и вычислений (лекции). Новосибирский Государственный университет: Новосибирск, 1967.
• Конечные автоматы (поведение и синтез, совместно с Я. М. Барздинем). Наука: Москва, 1970.

• Finite Automata (Behavior and Synthesis, на английском языке). В серии «Fundamental Studies in Computer Science». North-Holland Publishing Company: Амстердам—Лондон, 1973 и American Elsevier Publishing Company: Нью-Йорк, 1973.

• Алгоритмы и вычислительные автоматы. Советское радио: Москва, 1974.

• Algorithmen und Rechenautomaten (на немецком языке). Deutsche Verlag der Wissenschaften: Берлин, 1977.
• Što su algoritmi: algoritmi i računski automati (на хорватском языке). Školska Knjiga: Загреб, 1978.
• Algoritmusok és absztrakt automaták (на венгерском языке). Műszaki Könyvkiadó: Будапешт и Мир: Москва, 1978.

• Selected Developments in Soviet Mathematical Cybernetics. Delphic Associated: Вашингтон, 1985.
• Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday (см. электронное издание [dblp.uni-trier.de/db/conf/birthday/trakhtenbrot2008.html здесь]). Lecture Notes in Computer Science (Введение: From Logic to Theoretical Computer Science, стр. 1—39). Springer: Нью-Йорк, 2008.

Ссылки

• [www2.tau.ac.il/cs/page.asp?fname=Boris&lname=Trakhtenbrot Страница Б. Трахтенброта на сайте Тель-Авивского университета]  (англ.)
• [www.math.psu.edu/simpson/courses/math457/trakh.pdf Подробный обзор теоремы Трахтенброта]
• [yessenin-volpin.org/images/seminar%20in%20mathematical%20logic,%201950's.jpeg Слева направо: А. А. Марков, В. А. Успенский, С. А. Адян, Б. А. Трахтенброт. Стоит: А. С. Есенин-Вольпин. Москва, 1950] (недоступная ссылка с 13-05-2013 (4002 дня) — история)
• [dblp.uni-trier.de/db/indices/a-tree/t/Trakhtenbrot:Boris_A=.html List of publications from the DBLP Bibliography Server]  (англ.)

Отрывок, характеризующий Трахтенброт, Борис Авраамович

– Это тот Илья Ростов, который женился на Nathalie Шиншиной, – сказала Анна Михайловна.
– Знаю, знаю, – сказал князь Василий своим монотонным голосом. – Je n'ai jamais pu concevoir, comment Nathalieie s'est decidee a epouser cet ours mal – leche l Un personnage completement stupide et ridicule.Et joueur a ce qu'on dit. [Я никогда не мог понять, как Натали решилась выйти замуж за этого грязного медведя. Совершенно глупая и смешная особа. К тому же игрок, говорят.]
– Mais tres brave homme, mon prince, [Но добрый человек, князь,] – заметила Анна Михайловна, трогательно улыбаясь, как будто и она знала, что граф Ростов заслуживал такого мнения, но просила пожалеть бедного старика. – Что говорят доктора? – спросила княгиня, помолчав немного и опять выражая большую печаль на своем исплаканном лице.
– Мало надежды, – сказал князь.
– А мне так хотелось еще раз поблагодарить дядю за все его благодеяния и мне и Боре. C'est son filleuil, [Это его крестник,] – прибавила она таким тоном, как будто это известие должно было крайне обрадовать князя Василия.
Князь Василий задумался и поморщился. Анна Михайловна поняла, что он боялся найти в ней соперницу по завещанию графа Безухого. Она поспешила успокоить его.
– Ежели бы не моя истинная любовь и преданность дяде, – сказала она, с особенною уверенностию и небрежностию выговаривая это слово: – я знаю его характер, благородный, прямой, но ведь одни княжны при нем…Они еще молоды… – Она наклонила голову и прибавила шопотом: – исполнил ли он последний долг, князь? Как драгоценны эти последние минуты! Ведь хуже быть не может; его необходимо приготовить ежели он так плох. Мы, женщины, князь, – она нежно улыбнулась, – всегда знаем, как говорить эти вещи. Необходимо видеть его. Как бы тяжело это ни было для меня, но я привыкла уже страдать.
Князь, видимо, понял, и понял, как и на вечере у Annette Шерер, что от Анны Михайловны трудно отделаться.
– Не было бы тяжело ему это свидание, chere Анна Михайловна, – сказал он. – Подождем до вечера, доктора обещали кризис.
– Но нельзя ждать, князь, в эти минуты. Pensez, il у va du salut de son ame… Ah! c'est terrible, les devoirs d'un chretien… [Подумайте, дело идет о спасения его души! Ах! это ужасно, долг христианина…]
Из внутренних комнат отворилась дверь, и вошла одна из княжен племянниц графа, с угрюмым и холодным лицом и поразительно несоразмерною по ногам длинною талией.
Князь Василий обернулся к ней.
– Ну, что он?
– Всё то же. И как вы хотите, этот шум… – сказала княжна, оглядывая Анну Михайловну, как незнакомую.
– Ah, chere, je ne vous reconnaissais pas, [Ах, милая, я не узнала вас,] – с счастливою улыбкой сказала Анна Михайловна, легкою иноходью подходя к племяннице графа. – Je viens d'arriver et je suis a vous pour vous aider a soigner mon oncle . J`imagine, combien vous avez souffert, [Я приехала помогать вам ходить за дядюшкой. Воображаю, как вы настрадались,] – прибавила она, с участием закатывая глаза.
Княжна ничего не ответила, даже не улыбнулась и тотчас же вышла. Анна Михайловна сняла перчатки и в завоеванной позиции расположилась на кресле, пригласив князя Василья сесть подле себя.
– Борис! – сказала она сыну и улыбнулась, – я пройду к графу, к дяде, а ты поди к Пьеру, mon ami, покаместь, да не забудь передать ему приглашение от Ростовых. Они зовут его обедать. Я думаю, он не поедет? – обратилась она к князю.
– Напротив, – сказал князь, видимо сделавшийся не в духе. – Je serais tres content si vous me debarrassez de ce jeune homme… [Я был бы очень рад, если бы вы меня избавили от этого молодого человека…] Сидит тут. Граф ни разу не спросил про него.
Он пожал плечами. Официант повел молодого человека вниз и вверх по другой лестнице к Петру Кирилловичу.


Пьер так и не успел выбрать себе карьеры в Петербурге и, действительно, был выслан в Москву за буйство. История, которую рассказывали у графа Ростова, была справедлива. Пьер участвовал в связываньи квартального с медведем. Он приехал несколько дней тому назад и остановился, как всегда, в доме своего отца. Хотя он и предполагал, что история его уже известна в Москве, и что дамы, окружающие его отца, всегда недоброжелательные к нему, воспользуются этим случаем, чтобы раздражить графа, он всё таки в день приезда пошел на половину отца. Войдя в гостиную, обычное местопребывание княжен, он поздоровался с дамами, сидевшими за пяльцами и за книгой, которую вслух читала одна из них. Их было три. Старшая, чистоплотная, с длинною талией, строгая девица, та самая, которая выходила к Анне Михайловне, читала; младшие, обе румяные и хорошенькие, отличавшиеся друг от друга только тем, что у одной была родинка над губой, очень красившая ее, шили в пяльцах. Пьер был встречен как мертвец или зачумленный. Старшая княжна прервала чтение и молча посмотрела на него испуганными глазами; младшая, без родинки, приняла точно такое же выражение; самая меньшая, с родинкой, веселого и смешливого характера, нагнулась к пяльцам, чтобы скрыть улыбку, вызванную, вероятно, предстоящею сценой, забавность которой она предвидела. Она притянула вниз шерстинку и нагнулась, будто разбирая узоры и едва удерживаясь от смеха.
– Bonjour, ma cousine, – сказал Пьер. – Vous ne me гесоnnaissez pas? [Здравствуйте, кузина. Вы меня не узнаете?]
– Я слишком хорошо вас узнаю, слишком хорошо.
– Как здоровье графа? Могу я видеть его? – спросил Пьер неловко, как всегда, но не смущаясь.
– Граф страдает и физически и нравственно, и, кажется, вы позаботились о том, чтобы причинить ему побольше нравственных страданий.
– Могу я видеть графа? – повторил Пьер.
– Гм!.. Ежели вы хотите убить его, совсем убить, то можете видеть. Ольга, поди посмотри, готов ли бульон для дяденьки, скоро время, – прибавила она, показывая этим Пьеру, что они заняты и заняты успокоиваньем его отца, тогда как он, очевидно, занят только расстроиванием.
Ольга вышла. Пьер постоял, посмотрел на сестер и, поклонившись, сказал:
– Так я пойду к себе. Когда можно будет, вы мне скажите.
Он вышел, и звонкий, но негромкий смех сестры с родинкой послышался за ним.
На другой день приехал князь Василий и поместился в доме графа. Он призвал к себе Пьера и сказал ему:
– Mon cher, si vous vous conduisez ici, comme a Petersbourg, vous finirez tres mal; c'est tout ce que je vous dis. [Мой милый, если вы будете вести себя здесь, как в Петербурге, вы кончите очень дурно; больше мне нечего вам сказать.] Граф очень, очень болен: тебе совсем не надо его видеть.
С тех пор Пьера не тревожили, и он целый день проводил один наверху, в своей комнате.
В то время как Борис вошел к нему, Пьер ходил по своей комнате, изредка останавливаясь в углах, делая угрожающие жесты к стене, как будто пронзая невидимого врага шпагой, и строго взглядывая сверх очков и затем вновь начиная свою прогулку, проговаривая неясные слова, пожимая плечами и разводя руками.
– L'Angleterre a vecu, [Англии конец,] – проговорил он, нахмуриваясь и указывая на кого то пальцем. – M. Pitt comme traitre a la nation et au droit des gens est condamiene a… [Питт, как изменник нации и народному праву, приговаривается к…] – Он не успел договорить приговора Питту, воображая себя в эту минуту самим Наполеоном и вместе с своим героем уже совершив опасный переезд через Па де Кале и завоевав Лондон, – как увидал входившего к нему молодого, стройного и красивого офицера. Он остановился. Пьер оставил Бориса четырнадцатилетним мальчиком и решительно не помнил его; но, несмотря на то, с свойственною ему быстрою и радушною манерой взял его за руку и дружелюбно улыбнулся.
– Вы меня помните? – спокойно, с приятной улыбкой сказал Борис. – Я с матушкой приехал к графу, но он, кажется, не совсем здоров.
– Да, кажется, нездоров. Его всё тревожат, – отвечал Пьер, стараясь вспомнить, кто этот молодой человек.
Борис чувствовал, что Пьер не узнает его, но не считал нужным называть себя и, не испытывая ни малейшего смущения, смотрел ему прямо в глаза.
– Граф Ростов просил вас нынче приехать к нему обедать, – сказал он после довольно долгого и неловкого для Пьера молчания.
– А! Граф Ростов! – радостно заговорил Пьер. – Так вы его сын, Илья. Я, можете себе представить, в первую минуту не узнал вас. Помните, как мы на Воробьевы горы ездили c m me Jacquot… [мадам Жако…] давно.
– Вы ошибаетесь, – неторопливо, с смелою и несколько насмешливою улыбкой проговорил Борис. – Я Борис, сын княгини Анны Михайловны Друбецкой. Ростова отца зовут Ильей, а сына – Николаем. И я m me Jacquot никакой не знал.
Пьер замахал руками и головой, как будто комары или пчелы напали на него.
– Ах, ну что это! я всё спутал. В Москве столько родных! Вы Борис…да. Ну вот мы с вами и договорились. Ну, что вы думаете о булонской экспедиции? Ведь англичанам плохо придется, ежели только Наполеон переправится через канал? Я думаю, что экспедиция очень возможна. Вилльнев бы не оплошал!
Борис ничего не знал о булонской экспедиции, он не читал газет и о Вилльневе в первый раз слышал.
– Мы здесь в Москве больше заняты обедами и сплетнями, чем политикой, – сказал он своим спокойным, насмешливым тоном. – Я ничего про это не знаю и не думаю. Москва занята сплетнями больше всего, – продолжал он. – Теперь говорят про вас и про графа.
Пьер улыбнулся своей доброю улыбкой, как будто боясь за своего собеседника, как бы он не сказал чего нибудь такого, в чем стал бы раскаиваться. Но Борис говорил отчетливо, ясно и сухо, прямо глядя в глаза Пьеру.
– Москве больше делать нечего, как сплетничать, – продолжал он. – Все заняты тем, кому оставит граф свое состояние, хотя, может быть, он переживет всех нас, чего я от души желаю…
– Да, это всё очень тяжело, – подхватил Пьер, – очень тяжело. – Пьер всё боялся, что этот офицер нечаянно вдастся в неловкий для самого себя разговор.
– А вам должно казаться, – говорил Борис, слегка краснея, но не изменяя голоса и позы, – вам должно казаться, что все заняты только тем, чтобы получить что нибудь от богача.