Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

опять мысли вслух про машины Тюринга

Нашёл сегодня случайно ещё одну статью, которая рассматривает проблему решения "нерешаемых" с точки зрения теории вычислимости задач, с помощью физических "трюков". Я об этом писал полтора года назад примерно (дальнейшее в этой записи, предупреждаю, будет скорее всего непонятно без чтения той). Статья, к-ю я нашёл сегодня: 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, о чём я и написал полтора года назад в комменте. Об этом надо бы подумать отдельно.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments