танской империи, член Королевского ученого общества, математик, многие работы которого были поняты только в 70-х годах <..>, был найден мертвым в постели у себя дома в Вилмслоу. По полицейскому отчету, предположительно за день до этого он принял цианистый калий. Тьюрингу был 41 год. Рядом было найдено надкусанное яблоко, на которое был нанесен цианид. Он использовал этот реактив в опытах по электролитическому нанесению покрытия на ложки. Химические эксперименты были его любимым увлечением с десятилетнего возраста.

Одно их стихотворений Тьюринга:

Hyperboloids of wondrous Light Rolling for aye through Space and Time Harbour those waves which somehow Might Play out Gods holy pantomime.

Перевод 1.

Удивительный свет не прекращает вековых скитаний. Пронзая пространства завесы. Прими его, и он, быть может, откроет сценарий Божественной пьесы.

Перевод 2.

Сверкающий света поток

Не остановит пространство и время.

Замысел своей пьесы откроет Бог

Тому, кто примет знания бремя (или поток сей в темя).

4.5. эмиль пост

Эмиль Леон Пост родился в Польше в 1897 г. В возрасте семи лет его родители эмигрировали в Нью-Йорк *.

As а child growing up in Harlem, Post was especially interested in astronomy. Tragically, before age thirteen he lost his left arm in an accident. Post wrote to several observatories asking whether his handicap would exclude him from the profession of astronomy. While the response from Harvard College Observatory was encouraging ("there is no reason why you may not become eminent in astronomy"), the superintendent of the U.S. Naval Observatory wrote that "in my opinion the loss of your left arm would be a very serious handicap to your becoming a professional astronomer. In observational work

*По материалам сайта «Emil Leon Post Papers*: http: www.amphils0c.0rg/library/br0wser/p/p0st.htm

Э.Л. Пост

with iIlstrшxleIlts the use of both hands is necessary in all the work of this observatory."Discouraged, Post turned his intellect away from the heavens and toward mathematics.

After graduating from Townsend Harris High School, Post entered City College of New York. By the time he received a B.S. in mathematics in 1917, Post had already done much of the work for a paper on generalized differentiation that was eventually published in 1930. From 1917-1920 Post was a graduate student at Columbia University. His doctoral dissertation involved the mathematical study of systems of logic, specifically the application of the truth table method to the propositional calculus of Whitehead and Russells Principia Mathematica. Post was able to show that the axioms of propositional calculus were both complete and consistent with respect to the truth table method. This dissertation was to help form the foundation of modern proof theory.

Post spent the 1920-1921 academic year at Princeton on a postdoctoral fellowship. It was during this period that he continued to analyze the Principia Mathematica and began to grapple with a revolutionary idea that would become famous in the 1930s: the fundamental incompleteness of any formal logic. Unfortunately for Post, his early formulations were fragmentary and as he struggled to work them out, Kurt Godel, who had no knowledge of Posts work, announced his landmark "incompleteness theorem"in 1931.

In 1936 Post contributed a paper to the first issue of the Journal of Symbolic Logic entitled "Finite Combinatory Processes - Formulation I."This paper had much in common with Alan Turings work on a universal computing machine. While Turings work described the mechanics of such a machine. Post focused on the instructions, or "software,"that would make the machine work. Post was able to prove that all computational processes could be reduced to a set of instructions that manipulated two symbols, "0"and "1."

Пост боролся с манигшальной депрессией в течение всей своей жизни. В 1954 году Пост умер от инфаркта, настигшего его после

Рис. 4.3:

(1897-1954).

электрошкоковой терапии в нью-йоркской больнице.

4.6. Эффективные алгоритмы

Алгоритм, трудоемкость которого (число шагов) ограничена полиномом от характерного размера задачи, назьшается эффективным.

Пример 4.6. (Жадный алгоритм). Рассмотрим конечное множество X, содержащее п элементов, некоторое семейство его подмножеств X С 2 и (весовую) функцию w : X [0, -boo). Пусть

w{A) = шaw{B), w(B)=

ьввсх

Алгоритм, который в указанном семействе X выбирает подмножество А с максимальным значением (весом) w(A), называется жадным.

Жадный алгоритм является эффективным; количество его шагов составляет 0{п).

Пример 4.7. (Полный перебор). Дано конечное множество X = {ai,...,an}, содержащее п элементов, и предикат P{xi, ...,Хп)-Этот продикат не является симметричным, т.е. Р(...,х,...,у,...) ф Р{...,у, ...,х,...). Требуется найти набор элементов (а, ...,а;„) такой, что F(aij, ) = Т. Самое простое решение этой задачи состоит в том, что

перебираются все возможные перестановки (а,а) из п элементов с проверкой истинности предиката на них. Известно, что число перестановок равно п\. Следовательно, трудоемкость такого алгоритма полного перебора 0(п!). Поскольку п! растет с ростом п быстрее любого полинома степени п и быстрее, чем 2", то данный алгоритм не является эффективным.

4.7. Алгоритмически неразрешимые проблемы

Рассмотрим массовую задачу, т.е. класс П однотипных, похожих конкретных задач. Если для решения массовой задачи найден ал-горитм, решаюш;ий эту задачу, то о задаче говорят как об алгоритмически разрешимой проблеме.

Этот алгоритм находит решение для любой задачи из П.