|
|
Заседания Московского математического общества
27 октября 2009 г., г. Москва, ГЗ МГУ, аудитория 16-10
|
|
|
|
|
|
Тезис Черча–Тюринга: история и недавние продвижения
Ю. Ш. Гуревич Исследовательский центр Майкрософт в Редмонде, США
|
Количество просмотров: |
Эта страница: | 276 |
|
Аннотация:
Тезис Черча–Тюринга — это и основание, и историческое начало современной информатики. Тезис привел Тюринга к универсальной вычислительной машине, откуда открылся прямой путь, по крайней мере концептуально, к программируемым компьютерам.
Но почему мы принимаем тезис? Тщательный анализ показывает, что обычные аргументы неубедительны. В связи с этим Курт Гедель думал, что, может быть, можно сформулировать аксиомы, которые схватывают суть вычислительных процессов, и потом формально вывести тезис Черча–Тюринга из этих аксиом. Это и есть то, что мы сделали (или по крайней мере попытались сделать) в недавней статье с Наумом Дершовицем из университета Тель Авива.
Помимо наших результатов, мне бы хотелось рассказать историю тезиса Черча–Тюринга. Эта увлекатеьная интеллектуальна драма разбросана по узкопрофессиональным и часто малоизвестнам изданиям.
|
|