Георгий Джапаридзе (также известный как Георгий Джапаридзе) - грузино-американский исследователь в области логики и теоретической информатики . В настоящее время он является профессором [1] факультета компьютерных наук Университета Вилланова . Джапаридзе наиболее известен своим изобретением логики вычислимости , кругового исчисления и полимодальной логики Джапаридзе .
Исследовать
В 1985–1988 [2] Джапаридзе разработал систему GLP, известную как полимодальная логика Джапаридзе . [3] [4] [5] [6] Это система модальной логики с операторами «необходимости» [0], [1], [2],…, понимаемыми как естественный ряд постепенно слабых предикатов доказуемости для Арифметика Пеано . В «Полимодальной логике доказуемости» [7] Джапаридзе доказал арифметическую полноту этой системы, а также присущую ей неполноту по отношению к фреймам Крипке . GLP широко изучался различными авторами в течение последующих трех десятилетий, особенно после того, как Лев Беклемишев в 2004 г. [8] указал на его полезность для понимания теории доказательств арифметики (алгебры доказуемости и ординалы теории доказательств ).
Джапаридзе также изучил версии первого порядка (предикатные) логики доказуемости. Он предложил аксиоматизацию фрагмента этой логики с одной переменной и доказал ее арифметическую полноту и разрешимость . [9] В той же статье он показал, что при условии 1-полноты лежащей в основе арифметической теории логика доказуемости предикатов с не повторяющимися модальностями рекурсивно перечислима . В [10] он сделал то же самое для логики доказуемости предиката с немодализованными кванторами.
В 1992–1993 годах Джапаридзе предложил концепции коинтерпретируемости , толерантности и сотолерантности , естественным образом возникающие в логике интерпретируемости . [11] [12] Он доказал, что коинтерпретируемость эквивалентна 1-консервативности, а толерантность эквивалентна 1-непротиворечивости. Первый был ответом на давнюю открытую проблему, касающуюся метаматематического смысла 1-консервативности. В рамках того же направления исследований Джапаридзе построил модальные логики толерантности [13] (1993 г.) и арифметической иерархии [14] (1994 г.) и доказал их арифметическую полноту. В 2002 году Джапаридзе представил «Логику задач» [15], которая позже стала частью его Семантики абстрактных ресурсов [16] [17], с одной стороны, и фрагментом логики вычислимости (см. Ниже), с другой стороны.
Джапаридзе наиболее известен [ цитата необходима ] как основатель Computability Logic в 2003 году и внесший последующий вклад в ее развитие. Это долгосрочная исследовательская программа и семантическая платформа для «перестройки логики как формальной теории (интерактивной) вычислимости, в отличие от формальной теории истины, которой она была более традиционно». [18] В 2006 году [19] Джапаридзе задумал круговое исчисление как теоретико-доказательный подход, который манипулирует конструкциями графического стиля, называемыми круговыми схемами, вместо более традиционных и менее общих древовидных конструкций, таких как формулы или секвенции. Этот новый теоретико-доказательный подход позже был успешно использован для «приручения» различных фрагментов логики вычислимости [20] [21], которая в остальном упорно сопротивлялась всем попыткам аксиоматизации с использованием традиционных систем доказательства, таких как исчисление секвенций или системы в стиле Гильберта . Он также использовался для (определения и) аксиоматизации чисто пропозиционального фрагмента независимой логики . [22] [23] [24] Рождение кругового исчисления сопровождалось предложением связанной с ним «семантики абстрактных ресурсов». Циркулярное исчисление с такой семантикой можно рассматривать как логику ресурсов, которая, в отличие от линейной логики , позволяет учитывать совместное использование ресурсов. Как таковая, она была представлена как жизнеспособная альтернатива линейной логике Джапаридзе, который неоднократно критиковал последнюю за то, что она недостаточно выразительна и не полна как ресурсная логика. Однако этот вызов остался в значительной степени незамеченным сообществом линейной логики, которое так и не ответило на него. [ необходима цитата ]
Джапаридзе бросило подобный (а также не ответили) вызов интуиционистской логики , [25] , критикуя его за отсутствие убедительного семантического ОБОСНОВАНИЯ связанного constructivistic претензий, и за то , что неполным в результате «выбрасывая ребенок с водой» . Интуиционистская логика Гейтинга в ее полной общности оказалась здравой [26], но неполной [27] с точки зрения семантики логики вычислимости. Однако было доказано, что позитивный (свободный от отрицания) пропозициональный фрагмент интуиционистской логики полон в отношении семантики логики вычислимости. [28] В статье «О системе логики вычислимости CL12» [29] на платформе логики вычислимости Джапаридзе обобщил традиционные концепции сложности времени и пространства на интерактивные вычисления и ввел третий вид меры сложности для таких вычислений. , получившее название «амплитудная сложность». Среди вкладов Джапаридзе является разработкой ряда систем (Пеано) арифметики на основе вычислимости логики, названный « clarithmetics ». [30] [31] [32] Сюда входят системы, ориентированные на сложность (в стиле ограниченной арифметики ) для различных комбинаций классов сложности по времени, пространству и амплитуде.
Биография и академическая карьера
Георгий Джапаридзе родился в 1961 году в Тбилиси , Грузия (тогда еще в Советском Союзе ). В 1983 году он окончил Тбилисский государственный университет , в 1987 году получил степень доктора философии в Московском государственном университете , а в 1998 году - вторую степень доктора философии (по информатике) в Пенсильванском университете. Старший научный сотрудник Института философии Академии наук Грузии . В 1992–1993 годах он был научным сотрудником Амстердамского университета (факультет математики и информатики). В 1993–1994 гг. Он занимал должность приглашенного доцента в Университете Нотр-Дам (факультет философии). Он поступил на факультет Университета Вилланова (факультет компьютерных наук). Джапаридзе также работал приглашенным профессором в Сямыньском университете (2007 г.) и Шаньдунском университете (2010–2013 гг.) В Китае . [33]
Награды
В 1982 году за свою работу «Детерминизм и свобода воли» Джапаридзе получил медаль Академии наук Грузии за лучшую студенческую исследовательскую работу, которая ежегодно присуждается одному студенту в стране. В 2015 году он получил Премию за выдающиеся научные исследования от Университета Вилланова, которая ежегодно присуждается одному преподавателю. [34] Джапаридзе был получателем различных грантов и стипендий, в то числе научно - исследовательских грантов от США Национального научного фонда , Университета Вилланова и Shandong University , докторантура от голландского правительства, Smullyan стипендий из Университета штата Индиана (не используется), и Fellowship Дины из Пенсильванского университета . [35]
Связанная библиография
- Пахомов Ф. « О сложности замкнутого фрагмента логики доказуемости Джапаридзе ». Архив математической логики 53 (2014), страницы 949-967.
- Д. Фернандес-Дуке и Дж. Йостен, " Хорошие порядки в трансфинитной алгебре Джапаридзе [ мертвая ссылка ] ". Логический журнал IGPL 22 (2014), страницы 933-963.
- В. Сюй, « Система высказываний, порожденная подходом Джапаридзе к логике IF [ мертвая ссылка ] ». Логический журнал IGPL 22 (2014), страницы 982-991.
- И. Шапировский, " PSPACE-разрешимость полимодальной логики Джапаридзе ". Успехи в модальной логике 7 (2008), страницы 289-304.
- Л.Д. Беклемишев, Дж. Дж. Йостен и М. Вервурт, « Окончательная обработка закрытого фрагмента логики доказуемости Джапаридзе ». Журнал логики и вычислений 15 (4) (2005), страницы 447-463.
- Булос Г. Аналитическая полнота полимодальной логики Джапаридзе . Анналы чистой и прикладной логики 61 (1993), страницы 95–111.
Избранные публикации
- Джапаридзе Г. « Построй свою собственную кларифметику I: Настройка и полнота ». Логические методы - информатика 12 (2016), выпуск 3, статья 8, страницы 1–59.
- Джапаридзе Г. « Построй свою собственную кларифметику II: Разумность ». Логические методы - информатика 12 (2016), выпуск 3, статья 12, страницы 1–62.
- Джапаридзе Г. « Введение в кларифметику II ». Информация и вычисления 247 (2016), страницы 290-312.
- Джапаридзе Г. « Введение в кларифметику III ». Анналы чистой и прикладной логики 165 (2014), страницы 241-252.
- Г. Джапаридзе, " Укрощение рекуррентностей в логике вычислимости с помощью кругового исчисления, Часть II ". Архив математической логики 52 (2013), страницы 213-259.
- Г. Джапаридзе, " Укрощение рекуррентностей в логике вычислимости с помощью циквного исчисления, Часть I ". Архив математической логики 52 (2013), страницы 173-212.
- Г. Джапаридзе, " Новое лицо ветвящейся повторяемости логики вычислимости ". Письма по прикладной математике 25 (2012), страницы 1585-1589.
- Джапаридзе Г. « Логическая основа конструктивных систем [ мертвая ссылка ] ». Журнал логики и вычислений 22 (2012), страницы 605-642.
- Джапаридзе Г. " Выделение основных логик основных повторений ". Анналы чистой и прикладной логики 163 (2012), страницы 377-389.
- Джапаридзе Г. « Введение в кларифметику I ». Информация и вычисления 209 (2011), страницы 1312-1354.
- Джапаридзе Г. От формул к схемам в логике вычислимости . Логические методы - это компьютерные науки 7 (2011 г.), выпуск 2, статья 1, страницы 1–55.
- Джапаридзе Г. " Переключающие операторы в логике вычислимости ". Теоретическая информатика 412 (2011), страницы 971-1004.
- Джапаридзе Г. « К прикладным теориям, основанным на логике вычислимости ». Журнал символической логики 75 (2010), страницы 565-601.
- Джапаридзе Г. « Многие концепции и две логики алгоритмической редукции ». Studia Logica 91 (2009), страницы 1–24.
- Г. Джапаридзе: « В начале была игровая семантика ». Игры: объединяющая логику, язык и философию. О. Майер, А.-В. Пьетаринен и Т. Туленхеймо, ред. Springer 2009, страницы 249-350.
- Джапаридзе Г. Последовательные операторы в логике вычислимости . Информация и вычисления 206 (2008), страницы 1443-1475.
- Джапаридзе Г., « Циркулярное исчисление углубилось [ мертвая ссылка ] ». Журнал логики и вычислений 18 (2008), страницы 983-1028.
- Джапаридзе Г. " Интуиционистский фрагмент логики вычислимости на уровне высказываний ". Анналы чистой и прикладной логики 147 (2007), страницы 187-227.
- Джапаридзе Г. Логика интерактивной редукции Тьюринга . Журнал символической логики 72 (2007), страницы 243-276.
- Джапаридзе Г. " Интуиционистская логика вычислимости ". Acta Cybernetica 18 (2007), страницы 77–113.
- Джапаридзе Г. « От истины к вычислимости II ». Теоретическая информатика 379 (2007), страницы 20–52.
- Джапаридзе Г. « От истины к вычислимости I ». Теоретическая информатика 357 (2006), страницы 100-135.
- Джапаридзе Г. « Введение в схемное исчисление и семантику абстрактных ресурсов ». Журнал логики и вычислений 16 (2006), страницы 489-532.
- Джапаридзе Г. " Логика вычислимости: формальная теория взаимодействия ". Интерактивные вычисления: новая парадигма. Д. Гольдин, С. Смолка и П. Вегнер, ред. Springer Verlag, Берлин, 2006 г., страницы 183-223.
- Джапаридзе Г. "Логика пропозициональной вычислимости II ". Транзакции ACM по вычислительной логике 7 (2006), страницы 331-362.
- Джапаридзе Г. "Логика пропозициональной вычислимости I ". Транзакции ACM по вычислительной логике 7 (2006), страницы 302-330.
- Джапаридзе Г. Введение в логику вычислимости . Анналы чистой и прикладной логики 123 (2003), страницы 1–99.
- Джапаридзе Г. Логика задач . Анналы чистой и прикладной логики 117 (2002), страницы 261-293.
- Джапаридзе Г. " Логика высказываний элементарных задач ". Журнал Нотр-Дам по формальной логике 41 (2000), № 2, страницы 171-183.
- Джапаридзе Г., ДеДжонг Д. Логика доказуемости . В: Справочник по теории доказательств, изд. С. Бусс, Северная Голландия, 1998 г., страницы 475-545.
- Джапаридзе Г. Конструктивная игровая семантика для языка линейной логики . Анналы чистой и прикладной логики 85 (1997), страницы 87–156.
- Г. Джапаридзе, " Простое доказательство арифметической полноты логики консервативности Пи-1 ". Журнал Нотр-Дам по формальной логике 35 (1994), страницы 346-354.
- Джапаридзе Г. Логика арифметической иерархии . Анналы чистой и прикладной логики 66 (1994), страницы 89–112.
- Джапаридзе Г. Обобщенное понятие слабой интерпретируемости и соответствующая модальная логика . Анналы чистой и прикладной логики 61 (1993), страницы 113-160.
- Джапаридзе Г. Логика линейной толерантности . Studia Logica 51 (1992), страницы 249-277.
- Джапаридзе Г. " Логика доказуемости предикатов с немодализованными кванторами ". Studia Logica 50 (1991), страницы 149-160.
- Г. Джапаридзе, " Разрешаемые и перечислимые логики предикатов доказуемости ". Studia Logica 49 (1990), страницы 7–21.
- С. Артемов, Г. Джапаридзе, " Конечные модели Крипке и предикатные логики доказуемости ". Журнал символической логики 55 (1990), страницы 1090-1098.
- Джапаридзе Г. Полимодальная логика доказуемости . Интенсиональная логика и логическая структура теорий. Мецниереба, Тбилиси, 1988, с. 16–48.
- С. Артемов, Г. Джапаридзе, "Об эффективных предикатных логиках доказуемости". Докады математики 297 (1987), стр. 521-523. Английский перевод в: Советская математика - Докл. 36, стр. 478-480.
Смотрите также
- Полимодальная логика Джапаридзе
Внешние ссылки
- Домашняя страница Георгия Джапаридзе
- Профессор Вилланова удостоен награды за исследования (статья Philadelphia Inquirer)
- Университет Вилланова выбирает профессора компьютерных наук лауреатом премии 2015 года за выдающиеся исследования факультета (пресс-релиз)
- Домашняя страница Computability Logic
- Семантика игр или линейная логика?
- Курс лекций по логике вычислимости
- О семантике абстрактных ресурсов и логике вычислимости (видеолекция Н. Верещагина)
Рекомендации
- ^ "Архивная копия" . Архивировано из оригинала на 2005-10-30 . Проверено 26 июня 2015 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ Г. Джапаридзе, " Полимодальная логика доказуемости ". Интенсиональная логика и логическая структура теорий. Мецниереба, Тбилиси, 1988, стр. 16-48.
- ^ Г. Булос, " Аналитическая полнота полимодальной логики Джапаридзе ". Анналы чистой и прикладной логики 61 (1993), страницы 95-111.
- ^ Л.Д. Беклемишев, JJ Joosten и М. Вервурт, " Окончательная обработка закрытого фрагмента логики доказуемости Джапаридзе ". Журнал логики и вычислений 15 (4) (2005), страницы 447-463.
- ^ И. Шапировский, " PSPACE-разрешимость полимодальной логики Джапаридзе ". Успехи в модальной логике 7 (2008), страницы 289-304.
- ^ Ф. Пахомов, " О сложности замкнутого фрагмента логики доказуемости Джапаридзе ". Архив математической логики 53 (2014), страницы 949-967.
- ^ Г. Джапаридзе, " Полимодальная логика доказуемости ". Интенсиональная логика и логическая структура теорий. Мецниереба, Тбилиси, 1988, стр. 16-48.
- ^ Л. Беклемишев, " Алгебры доказуемости и ординалы теории доказательства, I ". Анналы чистой и прикладной логики 128 (2004), страницы 103-123.
- ^ Г. Джапаридзе, " Разрешаемые и перечислимые логики предикатов доказуемости ". Studia Logica 49 (1990), страницы 7-21.
- ^ Г. Джапаридзе, " Логика доказуемости предикатов с немодализованными кванторами ". Studia Logica 50 (1991), страницы 149-160.
- ^ Г. Джапаридзе, " Логика линейной толерантности ". Studia Logica 51 (1992), страницы 249-277.
- ^ Г. Джапаридзе, " Обобщенное понятие слабой интерпретируемости и соответствующей модальной логики ". Анналы чистой и прикладной логики 61 (1993), страницы 113-160.
- ^ Г. Джапаридзе, " Обобщенное понятие слабой интерпретируемости и соответствующей модальной логики ". Анналы чистой и прикладной логики 61 (1993), страницы 113-160.
- ^ Г. Джапаридзе, " Логика арифметической иерархии ". Анналы чистой и прикладной логики 66 (1994), страницы 89-112.
- ^ Г. Джапаридзе, « Логика задач ». Анналы чистой и прикладной логики 117 (2002), страницы 261-293.
- ^ Г. Джапаридзе, " Введение в круговое исчисление и семантику абстрактных ресурсов ". Журнал логики и вычислений 16 (2006), страницы 489-532.
- ^ И. Межиров и Н. Верещагин, " Об абстрактной семантике ресурсов и логике вычислимости ". Журнал компьютерных и системных наук 76 (2010), страницы 356-372.
- ^ Г. Джапаридзе, « Введение в кларифметику I ». Информация и вычисления 209 (2011), страницы 1312-1354.
- ^ Г. Джапаридзе, " Введение в круговое исчисление и семантику абстрактных ресурсов ". Журнал логики и вычислений 16 (2006), страницы 489-532.
- ^ Г. Джапаридзе, " Укрощение рекуррентности в логике вычислимости через циквное исчисление, Часть I ". Архив математической логики 52 (2013), страницы 173-212.
- ^ Г. Джапаридзе, " Укрощение рекуррентности в логике вычислимости с помощью кругового исчисления, Часть II ". Архив математической логики 52 (2013), страницы 213-259.
- ^ Г. Джапаридзе, « От формул к схемам в логике вычислимости ». Логические методы - это компьютерные науки 7 (2011 г.), выпуск 2, статья 1, страницы 1-55.
- ^ Г. Джапаридзе, "О системе CL12 логики вычислимости". Логические методы в информатике (в печати).
- ^ В. Сюй, " Система высказываний, вызванная подходом Джапаридзе к логике IF [ мертвая ссылка ] ". Логический журнал IGPL 22 (2014), страницы 982-991.
- ^ Г. Джапаридзе, « Вначале была семантика игры ». Игры: объединяющая логику, язык и философию. О. Майер, А.-В. Пьетаринен и Т. Туленхеймо, ред. Springer 2009, страницы 249-350.
- ^ Г. Джапаридзе, " Интуиционистская логика вычислимости ". Acta Cybernetica 18 (2007), страницы 77-113.
- ^ И. Межиров и Н. Верещагин, " Об абстрактной семантике ресурсов и логике вычислимости ". Журнал компьютерных и системных наук 76 (2010), страницы 356-372.
- ^ Г. Джапаридзе, " Интуиционистский фрагмент логики вычислимости на пропозициональном уровне ". Анналы чистой и прикладной логики 147 (2007), страницы 187-227.
- ^ Г. Джапаридзе, " О системе CL12 логики вычислимости ". Логические методы - информатика (в печати).
- ^ Г. Джапаридзе, « К прикладным теориям, основанным на логике вычислимости. Архивировано 29 июня 2015 г. на Wayback Machine ». Журнал символической логики 75 (2010), страницы 565-601.
- ^ Г. Джапаридзе, « Введение в кларифметику I ». Информация и вычисления 209 (2011), страницы 1312-1354.
- ^ Г. Джапаридзе, « Введение в кларифметику III ». Анналы чистой и прикладной логики 165 (2014), страницы 241-252.
- ^ [1] Домашняя страница Георгия Джапаридзе
- ^ Профессор Вилланова, удостоенный награды за исследования (статья Philadelphia Inquirer)
- ^ Георгий Джапаридзе: Исследования и публикации