Может вероятностный алгоритм решить halting problem?

[tenmin]

Существует ли вероятностный алгоритм, который с вероятностью 99,99999999% для любой программы $P$ и входных данных $D$ определяет остановится или нет процесс вычисления $P(D)$?

[patzer2097]

Ваши попытки решения?
Впрочем, если Вы такой алгоритм разработали и хотите нас с ним познакомить, то Вам лучше писать в другой подфорум

[tenmin]

patzer2097 в сообщении #886557 писал(а):

Ваши попытки решения?

Мне кажется, что такой алгоритм есть потому, что обычное доказательство неразрешимости проблемы останова не сработает в случае если алгоритм может иногда давать неверные ответы. Чтобы доказать существование чего-то, обычно строят пример. Я не знаю как его построить.

patzer2097 в сообщении #886557 писал(а):

Впрочем, если Вы такой алгоритм разработали и хотите нас с ним познакомить, то Вам лучше писать в другой подфорум

И что же тут такого веселого?

[Aritaborian]

Круто вы тут пытаетесь всех запутать. У вас что, программа $P$ тоже подразумевается недетерминированной?

[tenmin]

Aritaborian
Сорри, $P$ предполагается детерминированной. Забыл сказать.

[Aritaborian]

tenmin в сообщении #886572 писал(а):

обычное доказательство неразрешимости проблемы останова не сработает в случае если алгоритм может иногда давать неверные ответы.

В этой части предложения ведь под алгоритмом понимается программа $P$?

[tenmin]

Aritaborian в сообщении #886580 писал(а):

В этой части предложения ведь под алгоритмом понимается программа $P$?

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

[Aritaborian]

tenmin в сообщении #886581 писал(а):

Нет, алгоримт, существование которого я спрашивал в первом посте.

Вы крайне невнятно выражаетесь.

tenmin в сообщении #886581 писал(а):

Программа и алгоритм это вообще разные вещи, кстати.

Да неужто? В нашем случае это именно одно и то же. Расскажите, в чём разница между этими двумя понятиями, раз уж так считаете.

[tenmin]

Aritaborian в сообщении #886584 писал(а):

Да неужто? В нашем случае это именно одно и то же. Расскажите, в чём разница между этими двумя понятиями, раз уж так считаете.

Например, машина Тьюринга (алгоритм) - это семерка объектов. Пусть $f$ каждой МТ однозначно ставит в соответствие слово в алфавите, например, $\{0,1\}$. Если $A$ - МТ, то $f(A)$ - соотвтетствующая ей программа.
Мне кажется я читал какую-то книгу в которой использовались такие определения, не помню в какой.

[patzer2097]

tenmin в сообщении #886572 писал(а):

Мне кажется, что такой алгоритм есть потому, что обычное доказательство неразрешимости проблемы останова не сработает в случае если алгоритм может иногда давать неверные ответы.

Мне кажется, что 2+2=5 потому, что обычное доказательство $2+2=4$ не сработает в случае если двойки написаны жирным шрифтом.

[Aritaborian]

tenmin в сообщении #886586 писал(а):

Например, машина Тьюринга (алгоритм) - это семерка объектов.

А Linux Mint — это восьмёрка объектов. А Microsoft Windows XP так вообще дюжина объектов.

tenmin в сообщении #886586 писал(а):

Мне кажется я читал какую-то книгу в которой использовались такие определения, не помню в какой.

Мне кажется, я читал какую-то книгу, в которой мужики в шляпах и плащах размахивали шпагами, не помню, что за книга была.

[patzer2097]

в общем, я голосую за закрытие темы

[tenmin]

Ясно, не форум, а клоунада. Пацанчики в тему чисто поржать зашли с, по их мнению, неуча. Не буду мешать.
Можете банить, я тут больше все равно писать не буду.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Крайне неопределенный предмет обсуждения. Уточните все определения и постановку вопроса.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.