Мур, Эдвард Форест

Родился 23 ноября в Балтиморе.

Мур получил степень бакалавра по математике в Политехническом Университете Виргинии в 1947 году и степень доктора наук по математике в Брауновском университете в июне 1950 года.

Работал в Иллинойсском университете в Урбане-Шампейне с 1950 по 1952 и был приглашённым лектором в МИТ и Гарвард одновременно в 1952 и 1953. Затем он работал в Bell Labs с 1951 по 1966 год в Исследовательском отделе коммутации. Впоследствии был профессором в университете Висконсин-Мадисон с 1966 и вплоть до выхода на пенсию в 1985 году^[1].

Скончался 14 июня 2003 года в Мадисоне.

29 июля 1950 года женился на Элинор Константе Мартин, у них было три дочери: Нэнси, Ширли и Марта^[2].

Мур был первым, кто использовал наиболее распространённый в наши дни тип конечного автомата: автомат Мура. Эта концепция была представлена в статье «Gedanken-experiments on Sequential Machines» в 1956 году^[3]. Совместно с Клодом Шенноном Мур проделал плодотворную работу по теории вычислимости и построению надёжных схем. В их совместной работе «Reliable Circuits Using Less Reliable Relays» (1956) была математически доказана возможность создания надёжных схем из ненадежных реле^[4].

Эдвард Мур внёс значительный вклад в теорию клеточных автоматов. В его честь названа «окрестность Мура» — концепция, определяющая совокупность центральной клетки и восьми смежных с ней ячеек (четыре по ортогонали и четыре по диагонали) на двумерной квадратной решётке. Эта модель применяется, в частности, в известной игре «Жизнь»^[5].

В 1962 году Мур совместно с Джоном Майхиллом стал соавтором доказательства теоремы «Садов Эдема» (англ. Garden of Eden theorem)^[5][6].

Мур также является одним из пионеров в области искусственной жизни. В 1956 году в статье для журнала Scientific American он предложил концепцию «искусственных живых растений» — гипотетических самовоспроизводящихся машин. Они описывались как плавучие фабрики, способные создавать собственные копии, используя солнечную энергию и извлекая из окружающей среды воду, воздух и минералы^[7].

В 1957 году на симпозиуме в Гарвардском университете Мур представил статью «Кратчайший путь через лабиринт» (англ. The shortest path through a maze, опубликована в 1959 году), в которой предложил один из первых алгоритмов нахождения кратчайшего пути в невзвешенном графе. Этот метод по своей сути является одной из форм поиска в ширину (BFS)^[8].

Мур первым поставил задачу описания и классификации регулярных графов, которые для заданных степени и диаметра достигают максимального теоретически возможного числа вершин (так называемая «граница Мура»). В 1960 году Алан Хоффман и Роберт Синглтон назвали такие графы в его честь «графами Мура»^[9]. Множество последних лет своей жизни он потратил на бесплодные усилия в решении проблемы четырёх красок.

• «Gedanken-experiments on Sequential Machines» (1956) — опубликована в сборнике «Automata Studies» под редакцией К. Шеннона и Дж. Маккарти^[3]$
• «Reliable Circuits Using Less Reliable Relays» (1956) — в соавторстве с К. Шенноном^[4]$
• «Artificial Living Plants» (1956) — статья в журнале Scientific American^[7]$
• «The shortest path through a maze» (1959)^[8].