Дэна Стюарт Скотт (родился 11 октября 1932 года) — американский логик, почётный профессор компьютерных наук , философии и математической логики в Университете Карнеги — Меллона ; сейчас он на пенсии и живёт в Беркли, Калифорния . Его работа по теории автоматов принесла ему премию Тьюринга в 1976 году, а его совместная работа с Кристофером Стрейчи в 1970-х годах заложила основы современных подходов к семантике языков программирования . Он также работал над модальной логикой , топологией и теорией категорий .
Он получил степень бакалавра по математике в Калифорнийском университете в Беркли в 1954 году. Он написал докторскую диссертацию по теме «Сходящиеся последовательности полных теорий» под руководством Алонзо Чёрча , работая в Принстоне , и защитил её в 1958 году. Соломон Феферман (2005) пишет об этом периоде:
Скотт начал изучать логику в Беркли в начале 50-х годов, еще будучи студентом. Его необычные способности вскоре были признаны, и он быстро перешел на аспирантские курсы и семинары с Тарским и стал частью группы, которая его окружала, включая меня и Ричарда Монтегю ; так что именно в то время мы подружились. Скотт явно был в курсе того, чтобы получить докторскую степень вместе с Тарским, но они поссорились по причинам, изложенным в нашей биографии. [1] Расстроенный этим, Скотт уехал в Принстон, где получил докторскую степень под руководством Алонзо Черча. Но прошло совсем немного времени, прежде чем отношения между ними наладились до такой степени, что Тарский мог сказать ему: «Надеюсь, я могу называть тебя своим учеником».
После окончания докторантуры он перешёл в Чикагский университет , где проработал преподавателем до 1960 года. В 1959 году он опубликовал совместную работу с Майклом О. Рабином , коллегой из Принстона, под названием « Конечные автоматы и проблема их принятия решений» (Скотт и Рабин, 1959), в которой в теорию автоматов была введена идея недетерминированных машин . Эта работа привела к совместному вручению им обоим премии Тьюринга за введение этой фундаментальной концепции теории вычислительной сложности .
Скотт занял должность доцента математики в Калифорнийском университете в Беркли и занялся классическими проблемами математической логики , особенно теорией множеств и теорией моделей Тарского . Он доказал, что аксиома конструктивности несовместима с существованием измеримого кардинала , и этот результат считается основополагающим в развитии теории множеств. [2]
В этот период он начал руководить аспирантами, такими как Джеймс Хэлперн ( Вклад в изучение независимости аксиомы выбора ) и Эдгар Лопес-Эскобар ( Бесконечно длинные формулы со счетными степенями квантификаторов ).
Скотт также начал работать над модальной логикой в этот период, начав сотрудничество с Джоном Леммоном , который переехал в Клермонт, Калифорния , в 1963 году. Скотт был особенно заинтересован в подходе Артура Прайора к временной логике и связи с трактовкой времени в семантике естественного языка, и начал сотрудничать с Ричардом Монтегю (Copeland 2004), которого он знал со времен своего обучения в Беркли. Позже Скотт и Монтегю независимо друг от друга открыли важное обобщение семантики Крипке для модальной и временной логики, названное семантикой Скотта-Монтегю (Scott 1970).
Джон Леммон и Скотт начали работу над учебником по модальной логике, которая была прервана смертью Леммона в 1966 году. Скотт распространил незавершенную монографию среди коллег, представив ряд важных методов в семантике теории моделей, наиболее важным из которых было представление уточнения канонической модели , которая стала стандартной, и введение техники построения моделей посредством фильтраций , обе из которых являются основными концепциями в современной семантике Крипке (Blackburn, de Rijke и Venema, 2001). Скотт в конечном итоге опубликовал работу как «Введение в модальную логику» (Lemmon & Scott, 1977).
Следуя первоначальному наблюдению Роберта Соловея , Скотт сформулировал концепцию булевозначной модели , как это сделали Соловей и Петр Вопенка примерно в то же время. В 1967 году Скотт опубликовал статью « Доказательство независимости гипотезы континуума» , в которой он использовал булевозначные модели для предоставления альтернативного анализа независимости гипотезы континуума по сравнению с тем, что предоставил Пол Коэн . Эта работа привела к присуждению премии Лероя П. Стила в 1972 году.
В 1972 году Скотт занял должность профессора математической логики на философском факультете Оксфордского университета. Во время учебы в Оксфорде он был членом Мертон-колледжа , а сейчас является почетным членом этого колледжа.
В этот период Скотт работал с Кристофером Стрейчи , и им обоим удалось, несмотря на административное давление, [ требуется разъяснение ] выполнить работу по предоставлению математической основы для семантики языков программирования, работу, по которой Скотт наиболее известен [ мнение ] . Вместе их работа представляет собой подход Скотта–Стрейчи к денотационной семантике , важный и основополагающий вклад в теоретическую информатику . Одним из вкладов Скотта является его формулировка теории доменов , позволяющая программам, включающим рекурсивные функции и конструкции управления циклами, придавать денотационную семантику. Кроме того, он заложил основу для понимания бесконечной и непрерывной информации с помощью теории доменов и своей теории информационных систем .
Работа Скотта в этот период привела к награждению:
В Университете Карнеги-Меллона Скотт предложил теорию эквилогических пространств в качестве теории-преемницы теории доменов; среди ее многочисленных преимуществ, категория эквилогических пространств является декартово замкнутой категорией , тогда как категория доменов [3] таковой не является. В 1994 году он был принят в члены Ассоциации вычислительной техники . В 2012 году он стал членом Американского математического общества . [4]