тезис Чёрча — Тьюринга
От: Vaako Украина  
Дата: 24.04.14 07:44
Оценка: :))
Итак у нас есть вот это:
Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

Предлагаю пример программы решающую задачу, которую машина Тюринга решить не может.
Некоторое время назад я решил, что существуют задачи, которые чисто формально решить невозможно.
Например, для группы математиков невозможно узнать авторство каждого используемого ими символа, какими бы правилами эти математики не пользовались.
Отсюда напрашивается интересный вывод, что если часть задачи переложить на плечи программы, то получаемое решение не может быть вычислено машиной Тюринга никогда.

Попробую обрисовать программу. Математики будут набирать и редактировать текст с помощью программы, у каждого математика будет свой логин и пароль для захода в программу. Правила одновременного доступа к тексту можно взять такие как в SVN например. Следовательно, теперь программа сможет в любой момент времени указать кто был инициатором появления каждого символа в любой момент времени.

Машина Тюринга может представить программу такую программу в этом проблем нет. Но есть проблемы в получении конечного результата — ответить на вопрос кто автор каждого символа программа машина Тюринга не может. Проблема вот в чем. Несмотря на то, что до начала эксперимента машина Тюринга полностью представляет программу, формальная система представляющая эту машину не распалагает данными о действиях математиков. Для компьютерной программы в этом нет никаких проблем потому что программа это физический процесс и данные не обязательно должны быть известны на момент начала работы а могут возникать непредсказуемо в процессе работы.

Машина Тюринга с другой стороны это не физический процесс и все данные обязательно должны присутствовать на момент формулировки формальной системы иначе должны переформулироваться каждый раз когда новые данные возникают. Значит машина Тюринга со всеми входящими днными добвленными в качестве постулатов которая может получить в точности того же результат что и программа формльно отличается от машины Тюринга на момент начала эксперимента. Это будут две формально различные системы что и требовалось доказать.

Проблема усугубляется еще и тем что при любом действии со стороны математиков необходимо менять формальную систему представляющую машину Тюринга иначе данные заложенные в нее будут устаревшими. А поскольку машина Тюринга просто обязана быть сформулирована только один единственный раз, то очевидно сформулировать одну единственную машину Тюринга дающую в точности тот же результат что и программа невозможно.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.