Итак у нас есть вот это:
Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
Предлагаю пример программы решающую задачу, которую машина Тюринга решить не может.
Некоторое время назад я решил, что существуют задачи, которые чисто формально решить невозможно.
Например, для группы математиков невозможно узнать авторство каждого используемого ими символа, какими бы правилами эти математики не пользовались.
Отсюда напрашивается интересный вывод, что если часть задачи переложить на плечи программы, то получаемое решение не может быть вычислено машиной Тюринга никогда.
Попробую обрисовать программу. Математики будут набирать и редактировать текст с помощью программы, у каждого математика будет свой логин и пароль для захода в программу. Правила одновременного доступа к тексту можно взять такие как в SVN например. Следовательно, теперь программа сможет в любой момент времени указать кто был инициатором появления каждого символа в любой момент времени.
Машина Тюринга может представить программу такую программу в этом проблем нет. Но есть проблемы в получении конечного результата — ответить на вопрос кто автор каждого символа программа машина Тюринга не может. Проблема вот в чем. Несмотря на то, что до начала эксперимента машина Тюринга полностью представляет программу, формальная система представляющая эту машину не распалагает данными о действиях математиков. Для компьютерной программы в этом нет никаких проблем потому что программа это физический процесс и данные не обязательно должны быть известны на момент начала работы а могут возникать непредсказуемо в процессе работы.
Машина Тюринга с другой стороны это не физический процесс и все данные обязательно должны присутствовать на момент формулировки формальной системы иначе должны переформулироваться каждый раз когда новые данные возникают. Значит машина Тюринга со всеми входящими днными добвленными в качестве постулатов которая может получить в точности того же результат что и программа формльно отличается от машины Тюринга на момент начала эксперимента. Это будут две формально различные системы что и требовалось доказать.
Проблема усугубляется еще и тем что при любом действии со стороны математиков необходимо менять формальную систему представляющую машину Тюринга иначе данные заложенные в нее будут устаревшими. А поскольку машина Тюринга просто обязана быть сформулирована только один единственный раз, то очевидно сформулировать одну единственную машину Тюринга дающую в точности тот же результат что и программа невозможно.
Здравствуйте, Vaako, Вы писали:
V>Итак у нас есть вот это: V>Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
V>Предлагаю пример программы решающую задачу, которую машина Тюринга решить не может....
V... V>А поскольку машина Тюринга просто обязана быть сформулирована только один единственный раз, то очевидно сформулировать одну единственную машину Тюринга дающую в точности тот же результат что и программа невозможно.
Тут разница скорее всего в том, что у классической машины Тьюринга нет клавиатуры.
А если съэмулировать клавиатуру, например таким образом:
Каждой клавиатуре сопоставить ячейку на ленте, в неё будет записываться скан-код нажатой клавиши.
Машина будет постоянно просматривать эти ячейки, и совершать все действия, которые делает "настоящий" компьютер.
Естественно следует принять, что вся программа должна успеть отработать за время между нажатиями клавиш.
как-то так
Здравствуйте, Vaako, Вы писали:
V>все данные обязательно должны присутствовать на момент формулировки формальной системы иначе должны переформулироваться каждый раз когда новые данные возникают
Откуда взялось это странное ограничение? Входные данные МТ принадлежат области определения ЧРФ, которую она вычисляет — и это единственное "накладываемое" на них ограничение. Конкретная же последовательность цепочек элементов этого множества может не "присутствовать" ни на момент формулировки МТ, ни на момент ее запуска. Даже в ходе выполнения МТ оставшаяся часть этой последовательности также может не "присутствовать". В противном случае, существование универсальной МТ было бы под большим вопросом
Здравствуйте, icWasya, Вы писали:
W>Тут разница скорее всего в том, что у классической машины Тьюринга нет клавиатуры. W>А если съэмулировать клавиатуру, например таким образом: W>Каждой клавиатуре сопоставить ячейку на ленте, в неё будет записываться скан-код нажатой клавиши. W>Машина будет постоянно просматривать эти ячейки, и совершать все действия, которые делает "настоящий" компьютер. W>Естественно следует принять, что вся программа должна успеть отработать за время между нажатиями клавиш. W>как-то так
Вы предлагаете ввести абстрактную клавиатуру? Или наоборот, построить компьютер такой же убогий как и машина Тьюринга и поставить его делать то же что и современный компьютер с программой?
Что-то в обоих случаях не понял к чему вы клоните. То есть машина Тьюринга воспринимается как некая формальная система которая может в принципе решить любую задачу если ей дать достаточно времени. При этом задача должна быть сформулирована на момент начала работы такой машины.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Здравствуйте, Vaako, Вы писали:
V>>все данные обязательно должны присутствовать на момент формулировки формальной системы иначе должны переформулироваться каждый раз когда новые данные возникают
KV>Откуда взялось это странное ограничение? Входные данные МТ принадлежат области определения ЧРФ, которую она вычисляет — и это единственное "накладываемое" на них ограничение.
Если ЧРФ — это Частично рекурсивные функции, то разделение на МТ и область определения ЧРФ решению никак не поможет.
Во первых можно показать что вводимые данные могут быть частью программы,т.е. после внесения новых данных математиком программа перекомпилируется. Но суть в другом, а именно в представлении этих самых данных.
Если у нас есть МТ но нет данных то задача не решается по определению.
Знание области определения недостаточно, надо получить точный результат а не потенциальную возможность его получения.
Если есть и МТ, область определения ЧРФ и данные то тогда следующий вопрос, на какой момент времени определены эти данные?
Проблема как раз в этом и состоит. Мы моем определить данные такого рода только на определенный физический момент времени, причем физического времени действий математиков а не какого-то абстрактного времени.
Собственно это и очевидно, что формальная система работает только для данных которые можно вывести или которые постулированы на момент нахала рассуждений по такой формальной системе. Данные же которые на момент начала рассуждений неизвестны и появляются лишь в ходе рассуждений непредвиденным образом запрещены строгостью, поскольку для их включения приходится расширять и изменять формальную систему.
KV>Конкретная же последовательность цепочек элементов этого множества может не "присутствовать" ни на момент формулировки МТ, ни на момент ее запуска. Даже в ходе выполнения МТ оставшаяся часть этой последовательности также может не "присутствовать". В противном случае, существование универсальной МТ было бы под большим вопросом
Для программы безразлично когда появились данные в момент когда понадобились программе или еще до старта программы, а для абстрактной вычислительной машины это имеет значение. Лучше все на примере показать:
1) Были введены символы 2+2=4
2) После обработки информации программа рассчитала, что третий символ ввел математик-В а остальные математик-А:
2(А)+(А)2(В)=(А)4(А)
3) Область определения известна заранее — каждый символ принадлежит либо А либо В, но этого в общем случае не достаточно для получения результата (2)
4) машине Тьюринга потребуется дополнительная информация, которая на момент начала работы программы не известна и может быть задана только на некоторый физический момент времени. Как объединить физическое время с абстрактным вычислителем нужно расписать подробно. Собственно проблема в том, что математики полностью уверены что можно всегда отбросить физическую составляющую для каких угодно данных.
В приведенном примере мы не можем ее отбросить просто напросто. Вернее отбросив мы теряем возможность решать задачу.
Я почему, собственно, влез в тему-то... Дело в том, что описываемая вами задача "аутентифицировать пользователя на протяжении всего сеанса его работы с вычислителем" является подзадачей для "аутентифицировать пользователя на протяжении всего сеанса его работы с вычислителем, предоставляя ему возможность переводить вычислитель только в те состояния, которые допускает набор прав текущего пользователя". Т.е. не только "отслеживать" авторство каждого символа, но и разрешать или не разрешать вводить тот или иной символ или их последовательность. Последняя задача — широко известна в узких кругах, как одна из множества задач под общим названием "The General Security Problems", исследованных вдоль и поперек, причем практически в каждом исследовании приводится МТ, решающая такую задачу. Из относительно свежего: http://nob.cs.ucdavis.edu/bishop/notes/2008-cse-14/2008-cse-14.pdf
Т.е. то, что эта ваша задача прекрасно решается на МТ — факт, примерно с 76-года (когда вышла одна из первых работ на эту тему). А вот почему вы убедили себя в обратном, я честно говоря пока не понял =/ Если вы считаете, что после того, как МТ начнет свою работу, на ее ленте уже не может появиться никакой информации извне, то разумеется, это не так. МТ может разделять свою ленту с другой, параллельно-работающей МТ, реализующей, к примеру, процесс ввода математиками своих аутентификациионных данных и текста формул (та самая абстрактная клавиатура, да). При этом нас совершенно не должно волновать, как именно она устроена. Все, что нам нужно, это: а) знать то место на ленте, начиная с которого она будет печатать там вводимые символы (т.н. буферная зона) и б) обеспечить наличие головки основной МТ в начале этой зоны при переходе в состояние ожидания ввода.
Если же вся загвоздка в:
V>Как объединить физическое время с абстрактным вычислителем нужно расписать подробно.
то единицей времени для МТ принято считать один такт ее работы (однократное вычисление функции перехода из состояние в состояние). В чем здесь вы видите проблему? Если же вас смущает, что как ни крути, в нашей модели имеет место непонятно как и каким образом меняющееся упорядоченное множество элементов (ввод математиков), то подобные вещи разруливает такая абстракция, как "оракул" (http://en.wikipedia.org/wiki/Oracle_machine). Фактически, абстрактная клавиатура и будет являться оракулом, возвращающим либо пустой символ (в случае отсутствия новых введенных математиками символов), либо множество введенных на текущий момент времени (такт выполнения), но ранее не запрошенных у оракула символов.
V>Собственно проблема в том, что математики полностью уверены что можно всегда отбросить физическую составляющую для каких угодно данных.
Зря вы о них так. Математика, в которой рассматривается физическая составляющая — существует и называется "теоретическая физика". Правда, к теории вычислений она не имеет ни малейшего отношения)
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Я почему, собственно, влез в тему-то... Дело в том, что описываемая вами задача "аутентифицировать пользователя на протяжении всего сеанса его работы с вычислителем" является подзадачей для "аутентифицировать пользователя на протяжении всего сеанса его работы с вычислителем, предоставляя ему возможность переводить вычислитель только в те состояния, которые допускает набор прав текущего пользователя". Т.е. не только "отслеживать" авторство каждого символа, но и разрешать или не разрешать вводить тот или иной символ или их последовательность. Последняя задача — широко известна в узких кругах, как одна из множества задач под общим названием "The General Security Problems", исследованных вдоль и поперек, причем практически в каждом исследовании приводится МТ, решающая такую задачу. Из относительно свежего: http://nob.cs.ucdavis.edu/bishop/notes/2008-cse-14/2008-cse-14.pdf
Против этого я и не возражал. МТ полностью представляет программу до запуска или выдает в точности тот же результат если ему предоставить в точности те же данные которые поступили программе. Но остается проблема предоставления этих самых данных для МТ. Математики абстрагируются от этой фазы представляя что данные уже в наличии не важно каким образом. Нужно уточнить, что понимается под таким абстрагированием и как проходит этот процесс, поскольку для оговоренной задачи абстрагирование, вообще говоря, не получается провести.
KV>Т.е. то, что эта ваша задача прекрасно решается на МТ — факт, примерно с 76-года (когда вышла одна из первых работ на эту тему). А вот почему вы убедили себя в обратном, я честно говоря пока не понял =/ Если вы считаете, что после того, как МТ начнет свою работу, на ее ленте уже не может появиться никакой информации извне, то разумеется, это не так. МТ может разделять свою ленту с другой, параллельно-работающей МТ, реализующей, к примеру, процесс ввода математиками своих аутентификациионных данных и текста формул (та самая абстрактная клавиатура, да). При этом нас совершенно не должно волновать, как именно она устроена. Все, что нам нужно, это: а) знать то место на ленте, начиная с которого она будет печатать там вводимые символы (т.н. буферная зона) и б) обеспечить наличие головки основной МТ в начале этой зоны при переходе в состояние ожидания ввода.
Нет не сработает . Ничего из того что вы сказали проблемы не решает. Вы просто абстрагировались от проблемы никак ее не рассматривая. Следует рассматривать не программу, а ту задачу в решении которой она участвует. А это задача выяснения авторства символов. Программа помогает решать только часть задачи с точностью до определения авторизации в программе, а вот контроль за тем чтобы математики не пользовались логинами друг друга программа сделать не может.
Когда мы рассматриваем задачу в этом разрезе то очевидно, что поставив эксперимент в 10 лабораториях вы не сможете ни в одной из них получить с помощью МТ в точности тот же результата что и программа, поскольку вообще ничего не сказали о правилах и способах измерения тех данных которые нельзя ни вывести ни предсказать, а только измерить в определенное время определенным образом. И только после измерения включить в рассуждение или как входные данные для программы.
Для компьютерной программы это делать не нужно, так как она является физическим процессом который совершенно спокойно взаимодействует с физическим процессом который именуется математиком. В процессе нажатия клавиш происходит неявное измерение и интерпретация данных и данные поступают на обработку программе. А вот в случае с МТ нужно продемонстрировать что данный процесс можно игнорировать абстрагировавшись оттого как были получены данные. Такое абстрагирование возможно лишь при соблюдении некоторых условий. До начала работы и во время работы программы такое абстрагирование невозможно, а после завершения программы хотя у нас и будут все данные которые поступали на вход программы но на абстрагирование накладывается очень сильные ограничения.
Может быть начать с демонстрации такого МТ который выдает в точности тот результат что я огласил в формулировке задачи и посмотреть откуда вы берете данные в каких условиях вы их можете получить и как протекает процесс абстрагирования происхождения данных перед тем как попадает к МТ ?
Только пожалуйста не предлагайте заменить математика МТ потому что это не серьезно.
Вообще я не против всяких влезаний, они как раз и являются тем чем должна быть наука.
KV>Если же вся загвоздка в: V>>Как объединить физическое время с абстрактным вычислителем нужно расписать подробно. KV>то единицей времени для МТ принято считать один такт ее работы (однократное вычисление функции перехода из состояние в состояние). В чем здесь вы видите проблему? Если же вас смущает, что как ни крути, в нашей модели имеет место непонятно как и каким образом меняющееся упорядоченное множество элементов (ввод математиков), то подобные вещи разруливает такая абстракция, как "оракул" (http://en.wikipedia.org/wiki/Oracle_machine). Фактически, абстрактная клавиатура и будет являться оракулом, возвращающим либо пустой символ (в случае отсутствия новых введенных математиками символов), либо множество введенных на текущий момент времени (такт выполнения), но ранее не запрошенных у оракула символов.
Грубая логическая ошибка. Требуется привязка к реальному физическому времени математика. Виртуальное время МТ не имеет никакого смысла при решении данной задачи. Если такой привязки нет то данные вы получить не можете и потому взять их неоткуда. «Оракул» как раз и нужен был чтобы не говорить про измерения реальных физических величин. В контексте указанной задачи применить Оракула нет возможности. Если вы не измеряете в точности в момент физического происшествия то нет возможности говорить о данных вообще. Абстрагируясь от этого измерения вы полностью теряете возможность знать эти данные. Либо происходит измерение и сам этот факт включен в абстрактные рассуждения, либо о результатах измерения говорить запрещено.
Собственно, можем пойти и в обратном направлении. Покажите что можете абстрагироваться от происхождения данных и получить в точности тот же результат что и без абстрагирования и проведения реальных измерений.
V>>Собственно проблема в том, что математики полностью уверены что можно всегда отбросить физическую составляющую для каких угодно данных. KV>Зря вы о них так. Математика, в которой рассматривается физическая составляющая — существует и называется "теоретическая физика". Правда, к теории вычислений она не имеет ни малейшего отношения)
Экспериментальная физика на самом деле. Попробую наглядный пример привести. Если абстрагирование от любых физических составляющих возможно и работает, то значит вы можете подготовить данные для МТ за неделю до начала работы программы или через неделю после работы программы. Правильно? Вот это вам и надо продемонстрировать как вы собираетесь провернуть этот подвиг без машины времени? Поскольку либо данные еще нельзя измерять либо момент измерения вы уже упустили безвозвратно. Для получения в точности того же результата вам нужно проводить измерения в точно в нужный момент и сразу включать их в качестве данных для МТ, а это во первых требует постоянной замены того что вы называете данными а во-вторых такой результат будет актуален только на определенный момент времени и в следующим момент может уже полностью устареть.
Вы нигде не упоминали что результат работы МТ будет жестко привязан к реальному физическому времени и от этой зависимости уйти не получится.
Из чего я делаю вывод что вы не решили задачи.
Вот теперь я вижу, в каком месте у вас появляется ошибки в рассуждениях:
V>а вот контроль за тем чтобы математики не пользовались логинами друг друга программа сделать <b>не может</b>.
Не "не может", а "не должна".
V>Ничего из того что вы сказали проблемы не решает.
А проблемы и нет, как таковой, поскольку то, что вы ей считаете — не имеет отношения к вычислительному процессу в том его смысле, который вкладывается в это понятие в формулировке тезиса.
<метафора>
Вам дали счетные палочки и попросили с их помощью сложить два числа. Вы же, выложив из палочек на земле:
Здравствуйте, Vaako, Вы писали:
V>Здравствуйте, icWasya, Вы писали:
W>>Тут разница скорее всего в том, что у классической машины Тьюринга нет клавиатуры. W>>А если съэмулировать клавиатуру, например таким образом: W>>Каждой клавиатуре сопоставить ячейку на ленте, в неё будет записываться скан-код нажатой клавиши. W>>Машина будет постоянно просматривать эти ячейки, и совершать все действия, которые делает "настоящий" компьютер. W>>Естественно следует принять, что вся программа должна успеть отработать за время между нажатиями клавиш. W>>как-то так
V>http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 V>Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина).
V>Вы предлагаете ввести абстрактную клавиатуру? Или наоборот, построить компьютер такой же убогий как и машина Тьюринга и поставить его делать то же что и современный компьютер с программой?
Да именно это
V>Что-то в обоих случаях не понял к чему вы клоните. То есть машина Тьюринга воспринимается как некая формальная система которая может в принципе решить любую задачу если ей дать достаточно времени. При этом задача должна быть сформулирована на момент начала работы такой машины.
А компьютер почти так и работает.
Программа уже написана на момент начала работы.
Например, когда я пише эти строки, работает ОС, драйвер клавиатуры, браузер, и ещё куча программ.
Когда я нажму [Отправить], этот текст попадёт на сервер, где уже работают, как минимум база данных, ос и драйвера, и их никто не переписывает прямо сейчас.
МТ надо только съэмулировать все эти действия. Только добавить клавиатуру , например таким способам, как я указал.
Здравствуйте, kochetkov.vladimir, Вы писали:
KV>А проблемы и нет, как таковой, поскольку то, что вы ей считаете — не имеет отношения к вычислительному процессу в том его смысле, который вкладывается в это понятие в формулировке тезиса.
Проблема была поставлена предельно четко — получить с помощь МТ в точности тоже что и получила программа.
Вы не смогли решить задачу.
Потому ваши аргументы можно смело игнорировать
Здравствуйте, icWasya, Вы писали:
V>>Вы предлагаете ввести абстрактную клавиатуру? Или наоборот, построить компьютер такой же убогий как и машина Тьюринга и поставить его делать то же что и современный компьютер с программой? W>Да именно это
Ну тогда тезис нарушается, потому что кроме МТ появляются дополнительные приспособления.
Тезис же утверждал что только при помощи МТ представляющей программу, а оказывается еще чтото дополнительно требуется.
Но в любом случае остается вопрос как "правильные данные" попадут в эту виртуальную клавиатуру, другую МТ, Оракула или что либо что мы понапридумываем?
То есть тезис опровергается либо потому, что МТ не достаточно, либо потому, что у нас получается не абстрактный вычислитель а дополненный реальными измерительными устройствами.
V>>Что-то в обоих случаях не понял к чему вы клоните. То есть машина Тьюринга воспринимается как некая формальная система которая может в принципе решить любую задачу если ей дать достаточно времени. При этом задача должна быть сформулирована на момент начала работы такой машины.
W>А компьютер почти так и работает. W>Программа уже написана на момент начала работы. W>Например, когда я пише эти строки, работает ОС, драйвер клавиатуры, браузер, и ещё куча программ. W>Когда я нажму [Отправить], этот текст попадёт на сервер, где уже работают, как минимум база данных, ос и драйвера, и их никто не переписывает прямо сейчас. W>МТ надо только съэмулировать все эти действия. Только добавить клавиатуру :user: , например таким способам, как я указал.
В том то и дело что почти.
Это очень напоминает главную логическую проблему квантовой механики в случае редукции волновой функции. Пока не произойдет реального измерения можно сколько угодно логически рассуждать но так и не вычислить конкретное место попадания электрона.
Так и тут можно сколько угодно рассуждать что область значений вводимых математиком нам известно но логически вывести значение конкретного символа не получится, поскольку только конкретное измерение может предоставить данную информацию.
Другими словами мы должны в абстрактных рассуждениях вводить акт непосредственного прямого измерения некоторой реальной физической величины. Иначе просто не сможем продолжить логические рассуждения и, следовательно, получить результат о котором я говорил. Реальная же программа выдает правильный результат сразу же как только обработает данные на входе.
А все эти декларации о том, что задача уже была решена в 76 году не более чем заблуждения. В 76 году не было известно какую последовательность символов сгенерируют математики в 2014 году. Это физически невозможно узнать. Потому для того чтобы съэмулировать и просто абстрактно рассмотреть данные надо их откудато получить и даже получать постоянно после каждого действия математиков. А под абстрактным вычислителем в первую очередь понимается независимость от реального времени полученного результата. Вот этого как раз получить и не получается, если входные данные сильно зависят от физического времени то и выходные будут сильно зависеть.
, например таким способам, как я указал.
