Системы логики на основе порядковых чисел - Systems of Logic Based on Ordinals

Системы логики на основе порядковых чисел была докторская диссертация математик Алан Тьюринг.[1][2]

Тезис Тьюринга не касается нового типа формальной логики, и его не интересовали системы так называемой «ранжированной логики», производные от порядковой или относительной нумерации, в которых можно проводить сравнения между состояниями истинности на основе относительной достоверности. Вместо этого Тьюринг исследовал возможность разрешения условия гёделевской неполноты, используя метод бесконечностей Кантора. Это условие можно сформулировать так: во всех системах с конечным набором аксиом условие исключающего ИЛИ применяется к выразительной силе и доказуемости; то есть у человека может быть сила и отсутствие доказательства, или доказательство и отсутствие силы, но не то и другое одновременно.

Диссертация представляет собой исследование формальных математических систем после Теорема Гёделя. Гёдель показал, что для любой формальной системы S, достаточно мощной для представления арифметики, существует теорема G, которая верна, но система не может доказать. G можно было бы добавить в систему как дополнительную аксиому вместо доказательства. Однако это создало бы новую систему S 'со своей собственной недоказуемой истинной теоремой G' и так далее. Тезис Тьюринга рассматривает итерацию процесса до бесконечности, создавая систему с бесконечным набором аксиом.

Диссертация была завершена в Принстоне при Церковь Алонсо и была классической работой по математике, в которой была введена концепция порядковая логика.[3]

Мартин Дэвис утверждает, что хотя использование Тьюринга вычислительный оракул не является основной темой диссертации, она оказалась очень влиятельной в теоретическая информатика, например в полиномиальная временная иерархия.[4]

Рекомендации

  1. ^ Тьюринг, Алан (1938). Системы логики на основе порядковых чисел (Кандидатская диссертация). Университет Принстона. Дои:10.1112 / плмс / с2-45.1.161. HDL:21.11116 / 0000-0001-91CE-3. ProQuest  301792588.
  2. ^ Тьюринг, А. (1939). «Системы логики на основе порядковых чисел». Труды Лондонского математического общества: 161–228. Дои:10.1112 / плмс / с2-45.1.161. HDL:21.11116 / 0000-0001-91CE-3.
  3. ^ Соломон Феферман, Тьюринг в стране O (z) в "Универсальной машине Тьюринга: полувековой обзор" Рольфа Херкена, 1995 г. ISBN  3-211-82637-8 стр. 111
  4. ^ Мартин Дэвис «Вычислимость, вычисления и реальный мир», в Воображение и строгость отредактировал Сеттимо Термини 2006 ISBN  88-470-0320-2 страницы 63-66 [1]

внешняя ссылка