«Системы логики, основанные на ординалах» — докторская диссертация математика Алана Тьюринга . [1] [2]
Диссертация Тьюринга не касается нового типа формальной логики , и его не интересовали системы так называемой «ранговой логики», основанные на порядковой или относительной нумерации, в которых можно проводить сравнения между состояниями истинности на основе относительной достоверности. Вместо этого Тьюринг исследовал возможность решения гёделева условия неполноты с помощью метода бесконечностей Кантора .
Диссертация представляет собой исследование формальных математических систем на основе теоремы Гёделя . Гёдель показал, что для любой формальной системы S, достаточно мощной для представления арифметики, существует теорема G , которая верна, но система не может ее доказать. G можно добавить в систему в качестве дополнительной аксиомы вместо доказательства. Однако это создало бы новую систему S' со своей собственной недоказуемой истинной теоремой G' и так далее. В диссертации Тьюринга рассматривается, что произойдет, если вы просто повторяете этот процесс несколько раз, генерируя бесконечный набор новых аксиом, добавляемых к исходной теории, и даже идет еще на один шаг вперед в использовании трансфинитной рекурсии , чтобы пройти «за бесконечность», давая набор новых теории G α , по одной на каждое порядковое число α .
Диссертация была завершена в Принстоне под руководством Алонсо Чёрча и представляла собой классическую работу по математике, введшую концепцию порядковой логики . [3]
Мартин Дэвис утверждает, что, хотя использование Тьюрингом вычислительного оракула не является основным направлением диссертации, оно оказалось очень влиятельным в теоретической информатике , например, в иерархии с полиномиальным временем . [4]