опять мысли вслух про машины Тюринга
Nov. 18th, 2002 12:36 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНашёл сегодня случайно ещё одну статью, которая рассматривает проблему решения "нерешаемых" с точки зрения теории вычислимости задач, с помощью физических "трюков". Я об этом писал полтора года назад примерно (дальнейшее в этой записи, предупреждаю, будет скорее всего непонятно без чтения той). Статья, к-ю я нашёл сегодня: Non-Turing Computers and Non-Turing Computability by Mark Hogarth, в: PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association, 1994/1. В общем, это тот же способ обхода ограничений при помощи теории относительности, в некоторых специально сконструированных spacetimes по Минковскому. Основная идея такого "обхода" описана в старой записи; если кому-то интересны физические подробности, я могу вытащить статью в PDF и послать. С хронологической точки зрения это как раз не новая статья, а как раз старая; т.е. то, что я слышал полтора года назад, опиралось на эту статью 94-го года, по-видимому; и в ней упоминаяется здешний иерусалимский профессор Питовский, к-й как раз и читал лекцию полтора года назад.
Перечитал сейчас старую запись и комменты (в комментах там много важного для себя я написал).. . давно, наверное, можно было из этого хорошую статью сделать. По крайней мере, попробовать -- а я сидел на заднице, как обычно.
Я хотел, собственно, в этой записи привести только ссылку на эту статью, чтобы не потерялась... в самой статье ничего для меня нового нет, разве что Хогарт ухищрается ещё и решать не просто невычислимые задачи, но и рекурсивно неперечислимые (non-recursively enumerable) путём состыкования вместе бесконечного кол-ва "странных" участков с бесконечно ускоренным временем внутри одного пространства-времени... совсем беспредел какой-то. Но сейчас мне пришла в голову ещё забавная связь с недавней записью про неконструктивность теории вычислимости. Ведь там возникает ситуация, когда есть машина, решающая проблему (вычисляющая функцию F), но мы не знаем, какая это машина. И вполне естественным образом та же самая проблема возникает, когда мы пытаемся доказать, что какой-то "чёрный ящик" не решает halting problem, о чём я и написал полтора года назад в комменте. Об этом надо бы подумать отдельно.
Перечитал сейчас старую запись и комменты (в комментах там много важного для себя я написал).. . давно, наверное, можно было из этого хорошую статью сделать. По крайней мере, попробовать -- а я сидел на заднице, как обычно.
Я хотел, собственно, в этой записи привести только ссылку на эту статью, чтобы не потерялась... в самой статье ничего для меня нового нет, разве что Хогарт ухищрается ещё и решать не просто невычислимые задачи, но и рекурсивно неперечислимые (non-recursively enumerable) путём состыкования вместе бесконечного кол-ва "странных" участков с бесконечно ускоренным временем внутри одного пространства-времени... совсем беспредел какой-то. Но сейчас мне пришла в голову ещё забавная связь с недавней записью про неконструктивность теории вычислимости. Ведь там возникает ситуация, когда есть машина, решающая проблему (вычисляющая функцию F), но мы не знаем, какая это машина. И вполне естественным образом та же самая проблема возникает, когда мы пытаемся доказать, что какой-то "чёрный ящик" не решает halting problem, о чём я и написал полтора года назад в комменте. Об этом надо бы подумать отдельно.
