Системы логики, основанные на ординалах
«Системы логики, основанные на ординалах» — докторская диссертация математика Алана Тьюринга . [1] [2]
Диссертация Тьюринга не касается нового типа формальной логики , и его не интересовали системы так называемой «ранговой логики», основанные на порядковой или относительной нумерации, в которых можно проводить сравнения между состояниями истинности на основе относительной достоверности. Вместо этого Тьюринг исследовал возможность решения гёделева условия неполноты с помощью . метода бесконечностей Кантора
Диссертация представляет собой исследование формальных математических систем на основе теоремы Гёделя . Гёдель показал, что для любой формальной системы S, достаточно мощной для представления арифметики, существует теорема G , которая верна, но система не может ее доказать. G можно было бы добавить в систему в качестве дополнительной аксиомы вместо доказательства. Однако это создало бы новую систему S' со своей собственной недоказуемой истинной теоремой G' и так далее. В диссертации Тьюринга рассматривается, что произойдет, если вы просто повторяете этот процесс несколько раз, генерируя бесконечный набор новых аксиом, добавляемых к исходной теории, и даже идет еще на один шаг вперед в использовании трансфинитной рекурсии , чтобы пройти «за бесконечность», давая набор новых теории G α , по одной на каждое порядковое число α .
Диссертация была завершена в Принстоне под руководством Алонсо Чёрча и представляла собой классическую работу по математике, введшую концепцию порядковой логики . [3]
Мартин Дэвис утверждает, что, хотя использование Тьюрингом вычислительного оракула не является основным направлением диссертации, оно оказалось очень влиятельным в теоретической информатике , например, в иерархии с полиномиальным временем . [4]
Ссылки [ править ]
- ^ Тьюринг, Алан (1938). Системы логики на основе ординалов (кандидатская диссертация). Принстонский университет. дои : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 . ПроКвест 301792588 .
- ^ Тьюринг, AM (1939). «Системы логики, основанные на ординалах». Труды Лондонского математического общества : 161–228. дои : 10.1112/plms/s2-45.1.161 . hdl : 21.11116/0000-0001-91CE-3 .
- ↑ Соломон Феферман , Тьюринг в стране O(z) в «Универсальной машине Тьюринга: обзор полувека» Рольфа Херкена, 1995 г. ISBN 3-211-82637-8 стр. 111
- ^ Мартин Дэвис «Вычислимость, вычисления и реальный мир», в книге «Воображение и строгость» под редакцией Сеттимо Термини, 2006 г. ISBN 88-470-0320-2 страницы 63-66 [1]
Внешние ссылки [ править ]
- https://rauterberg.employee.id.tue.nl/lecturenotes/DDM110%20CAS/Turing/Turing-1939%20Sysyems%20of%20logic%20based%20on%20ordinals.pdf
- https://www.dcc.fc.up.pt/~acm/turing-phd.pdf
- https://web.archive.org/web/20121023103503/https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf
- «Принстонская диссертация Тьюринга» . Издательство Принстонского университета . Проверено 10 января 2012 г.
- Соломон Феферман (ноябрь 2006 г.), «Тезис Тьюринга» (PDF) , Уведомления AMS , 53 (10)
 | Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |
 | статья о математической публикации незавершена Эта . Вы можете помочь Википедии, расширив ее . |