![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
опять мысли вслух про машины Тюринга
Нашёл сегодня случайно ещё одну статью, которая рассматривает проблему решения "нерешаемых" с точки зрения теории вычислимости задач, с помощью физических "трюков". Я об этом писал полтора года назад примерно (дальнейшее в этой записи, предупреждаю, будет скорее всего непонятно без чтения той). Статья, к-ю я нашёл сегодня: 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, о чём я и написал полтора года назад в комменте. Об этом надо бы подумать отдельно.
no subject
no subject
а на чем у вас ещё есть варианты, простите, сидения?
Re:
Но в принципе много на чём можно сидеть, если воображение задействовать ;)
no subject
тезиса Тьюринга-Чёрча, путём описания процедуры построения автомата, который не может быть смоделирован машиной Тьюринга.
Не могу быть уверен на 100% в корректности доказательства, но мне оно показалось довольно убедительным. Естественно, это всё публиковалось, но вот в Интернет вроде бы не присутствует.
Re:
научные вопросы не являются предметом веры
отсутствие полной уверенности у меня лично было основано
на том, что просто не имел времени последовательно проверять
всю его теорию. Но насколько мне известно,
к ней был проявлен достаточно большой интерес среди
западных учёных, работающих по данной тематике,
чтобы мотивировать человека готовить английское издание
своей книги. Думаю, что после её выхода в свет
это доказательство либо будет опровергнуто, либо
факт перейдёт в категорию широкоизвестных.
no subject
Re:
no subject
(Anonymous) 2002-11-20 03:57 am (UTC)(link)Relativistic Computers and Non-uniform Complexity Theory
J. Wiedermann and Jan van Leeuwen, in
C.S. Calude, M.J. Dinneen, F. Peper (Eds.):
Unconventional Models of Computation Third International Conference, UMC 2002, Kobe, Japan, October 15-19, 2002,
LNCS 2509, p. 287 -- 299
==================================================
Recursive- and complexity-theoretic analysis of relativistic
Turing machines.
Lis
no subject
no subject
http://arxiv.org/abs/gr-qc/0209061
A computer which has access to a closed timelike curve, and can thereby send the results of calculations into its own past, can exploit this to solve difficult computational problems efficiently.
Не совсем о том же, но близко.
Re:
помогите с календарем
(Anonymous) 2011-12-02 11:00 am (UTC)(link)п.с. дали линки хз какая-то туфта [url=http://www.trexgorka.ru/media/school/kalendar-po-mesyacam.html]календарь по месяцам[/url]
и [url=http://www.trexgorka.ru/media/school/vyhodnoe-soprotivlenie.html]выходное сопротивление[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-15 11:48 pm (UTC)(link)и [url=http://www.mega.nn.ru/include/inc/rekviziti-moskovskogo-banka-sberbanka-rossii.html]реквизиты московского банка сбербанка россии[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-22 03:45 am (UTC)(link)и [url=http://www.catalysis.ru/resources/Catalystic/106/smotret-dikiy-angel-ekranka.html]смотреть дикий ангел экранка[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-23 01:08 pm (UTC)(link)и [url=http://www.mega.nn.ru/js/89/vzyatka-perevod.html]взятка перевод[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-28 03:29 am (UTC)(link)и [url=http://www.cci.donbass.com/media/system/swf/11/variatsii-v-lesu-rodilas-elochka.html]вариации в лесу родилась елочка[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-29 12:28 am (UTC)(link)и [url=http://www.mega.nn.ru/include/alt/opredelit-po-nomeru-mashini-vladeltsa.html]определить по номеру машины владельца[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-29 08:55 am (UTC)(link)и [url=http://www.fire.mchs.gov.ru/archive/photo/img/videleniya-v-promezhnosti.html]выделения в промежности[/url]
помощь профессиональному бухгалтеру
(Anonymous) 2012-01-29 06:08 pm (UTC)(link)и [url=http://www.fire.mchs.gov.ru/archive/photo/img/gibdd-varshavskoe-shosse-vremya-raboti.html]гибдд варшавское шоссе время работы[/url]