Ласло Кальмар: Жизнь и вклад в математическую логику и информатику.

Введение

Венгерский математик (1905–1976)

Математик Ласло Калмар (László Kalmár; 27 марта 1905 года, Эдде – 2 августа 1976 года, Матрахаза) — венгерский математик и профессор Сегедского университета. Калмара считают основоположником математической логики и теоретической информатики в Венгрии.

Биография

Кальмар происходил из еврейской семьи. Его ранняя жизнь была полна как надежд, так и трагедий. Его отец умер, когда он был молод, а мать – когда ему исполнилось 17 лет, в год поступления в Будапештский университет, что сделало его фактически сиротой. Талант Кальмара проявился еще в будапештских школах. В Будапештском университете его учителями были Кюршак и Фейер. Среди его сокурсников были будущий логик Рожа Полицер, а с 1934 года – Рожа Петер. Кальмар окончил университет в 1927 году. Математическую логику, область, которую он выбрал, он открыл для себя во время посещения Геттингена в 1929 году. После защиты докторской диссертации в Будапеште он получил должность в университете Сегеда. Этот университет в основном состоял из преподавателей бывшего Университета Колошвар, крупного венгерского университета до Первой мировой войны, который после войны оказался в Румынии. Колошвар был переименован в Клуж. Венгерский университет переехал в Сегед в 1920 году, где до этого университета не было. Назначение Хаара и Риеса превратило Сегед в крупный исследовательский центр математики. Кальмар начал свою карьеру в качестве ассистента Хаара и Риеса. В 1947 году Кальмар был назначен полным профессором в Сегеде. Он стал первым обладателем кафедры основ математики и информатики Сегедского университета. Он также основал Кибернетическую лабораторию Сегеда и Исследовательскую группу по математической логике и теории автоматов. В области математической логики Кальмар доказал, что определенные классы формул исчисления предикатов первого порядка разрешимы. В 1936 году он доказал, что исчисление предикатов можно сформулировать, используя единственный бинарный предикат, при условии, что рекурсивное определение терма достаточно полно. (Этот результат обычно приписывается статье Куайна 1954 года.) Он открыл альтернативную форму примитивно рекурсивной арифметики, известную как элементарно рекурсивная арифметика, основанную на примитивных функциях, отличающихся от общепринятых. Он приложил максимум усилий для развития компьютеров и информатики в Венгрии. Он писал о теоретической информатике, включая языки программирования, автоматическую коррекцию ошибок, нечисловые приложения компьютеров и связь между информатикой и математической логикой. Кальмар – один из немногих логиков, выразивших сомнения в тезисе Черча о том, что все интуитивно механистические, алгоритмические функции представимы рекурсивными функциями. В 1949 году Кальмар был избран членом Венгерской академии наук, а в 1950 и 1975 годах он был удостоен премии Кошута и Государственной премии Венгрии соответственно. В 1933 году Кальмар женился на Эрджебет Арвай, у них было четверо детей.

Kalmár was of Jewish ancestry. His early life mixed promise and tragedy. His father died when he was young, and his mother died when he was 17, the year he entered the University of Budapest, making him essentially an orphan. Kalmár's brilliance manifested itself while in Budapest schools. At the University of Budapest, his teachers included Kürschák and Fejér. His fellow students included the future logician Rózsa Politzer, from 1934 on Rózsa Péter. Kalmár graduated in 1927. He discovered mathematical logic, his chosen field, while visiting Göttingen in 1929. Upon completing his doctorate at Budapest, he took up a position at the University of Szeged. That university was mostly made up of staff from the former University of Kolozsvár, a major Hungarian university before World War I that found itself after the War in Romania. Kolozsvár was renamed Cluj. The Hungarian university moved to Szeged in 1920, where there had previously been no university. The appointment of Haar and Riesz turned Szeged into a major research center for mathematics. Kalmár began his career as a research assistant to Haar and Riesz. Kalmár was appointed a full professor at Szeged in 1947. He was the inaugural holder of Szeged's chair for the Foundations of Mathematics and Computer Science. He also founded Szeged's Cybernetic Laboratory and the Research Group for Mathematical Logic and Automata Theory. In mathematical logic, Kalmár proved that certain classes of formulas of the first order predicate calculus were decidable. In 1936, he proved that the predicate calculus could be formulated using a single binary predicate, if the recursive definition of a term was sufficiently rich. (This result is commonly attributed to a 1954 paper of Quine's.) He discovered an alternative form of primitive recursive arithmetic, known as elementary recursive arithmetic, based on primitive functions that differ from the usual kind. He did his utmost to promote computers and computer science in Hungary. He wrote on theoretical computer science, including programming languages, automatic error correction, non numerical applications of computers, and the connection between computer science and mathematical logic. Kalmar is one of the very few logicians who has raised doubts about Church's thesis that all intuitively mechanistic, algorithmic functions are representable by recursive functions. Kalmar was elected to the Hungarian Academy of Sciences in 1949, and was awarded the Kossuth Prize in 1950 and the Hungarian State Prize in 1975. In 1933 Kalmár married Erzsébet Arvay; they had four children.

Элементарные функции

Кальмар определил так называемые элементарные функции, арифметические функции (то есть основанные на натуральных числах), построенные на понятиях композиции и переменных, констант 0 и 1, повторного сложения + констант, вычитания с контролем неотрицательности ∸, ограниченного суммирования и ограниченного произведения (Клине 1952:526). Исключение ограниченного произведения из этого списка дает субелементарные или элементарные функции более низкого уровня. Используя абстрактную вычислительную модель, называемую машиной с регистрами, Швихтенберг демонстрирует, что "все элементарные функции вычислимы и полностью определены".