Алгоритмически неразрешимая задача

[AndreyXYZ]

Дана случайная последовательность $\{a_i\},\,a_i \in \{0,1\},\,P\{a_i=0\}=P\{a_i=1\}=\frac12,\,i=1,2,\ldots$
Найдем в последовательности $\{a_i\}$ первый от начала отрезок длины $n$, состоящий из одних единиц.
Введем функцию $f(n)$, равную номеру первого элемента этого отрезка.
Является ли эта задача нахождения $f(1)$ алгоритмически неразрешимой?

[General]

Отчего же? Вот, к примеру, для любой конкретной последоватлеьности задача решается алгоритмом
10 i=0
20 i=i+1
30 if a(i)=0 then goto 20
[40 print i

И задача нахождения математического ожидания номера первой единицы решается по формуле
$1*\frac{1}{2}+2*\frac{1}{4}+3*\frac{1}{8}+\dots=2$

Алгоритмически неразрешимая, вроде бы, другая - про поиск самой длинной цепочки из одних единиц в $\left{a_i\right}$

[hurtsy]

General в сообщении #245075 писал(а):

10 i=0
20 i=i+1
30 if a(i)=0 then goto 20
[40 print i

Объясните, пожалуйста, как Вы использовали n из условия AndreyXYZ. С уважением,

[General]

Так ведь просится найти $f(n)$ при $n=1$, т.е. иными словами - номер первой единицы.

[AndreyXYZ]

General в сообщении #245075 писал(а):

Отчего же? Вот, к примеру, для любой конкретной последоватлеьности задача решается алгоритмом
10 i=0
20 i=i+1
30 if a(i)=0 then goto 20
[40 print i

И задача нахождения математического ожидания номера первой единицы решается по формуле
$1*\frac{1}{2}+2*\frac{1}{4}+3*\frac{1}{8}+\dots=2$

Да, Вы написали алгоритм. Но никто не говорит, что этот алгоритм завершит свою работу на конечном шаге. Рассмотрим другую задачу. Найти первое вхождение отрезка длины $n$, состоящего из одних единиц, в десятичной записи числа $\pi$. Это задача является классической алгоритмически неразрешимой задачей, хотя для поиска её решения можно написать алгоритм.

[Xaositect]

У вас какое-то странное понятие алгоритмически неразрешимой задачи. Кажется, вы путаете частичные функции с неразрешимыми.

Как у нас стоит задача? Дана последовательность $a$, $f(a)$ равно первому символу первого отрезка из $n$ единиц, и не определено, если такого отрезка нет? Если так, то это (частичная) разрешимая задача.

[AndreyXYZ]

AndreyXYZ в сообщении #245276 писал(а):

Рассмотрим другую задачу. Найти первое вхождение отрезка длины $n$, состоящего из одних единиц, в десятичной записи числа $\pi$.

Эта задача является алгоритмически неразрешимой для всех $n$? Если да, то почему?

[hurtsy]

В принципе ответ уже сформулирован.

Xaositect в сообщении #245282 писал(а):

Если так, то это (частичная) разрешимая задача.

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

[Чудо-в-перьях]

а чем задача для числа $\pi$ отличается от задачи про поиск номера первой единицы?

[hurtsy]

Чудо-в-перьях в сообщении #246161 писал(а):

а чем задача для числа $\pi$ отличается от задачи про поиск номера первой единицы?

Задача про поиск номера первой единицы сформулирована несколько раз в этой теме, а задача о числе$\pi $ именно то, что Вы подумали, остальным нужна формулировка. С уважением,

[AndreyXYZ]

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

[maxal]

AndreyXYZ в сообщении #245041 писал(а):

Дана случайная последовательность $\{a_i\},\,a_i \in \{0,1\},\,P\{a_i=0\}=P\{a_i=1\}=\frac12,\,i=1,2,\ldots$

Если последовательность "дана" (что в алгоритмической задаче означает "написана"), то она не может быть случайной - и правильно говорить не о вероятностях появления 0 и 1, а об их частоте.

[AndreyXYZ]

maxal в сообщении #246527 писал(а):

AndreyXYZ в сообщении #245041 писал(а):

Дана случайная последовательность $\{a_i\},\,a_i \in \{0,1\},\,P\{a_i=0\}=P\{a_i=1\}=\frac12,\,i=1,2,\ldots$

Если последовательность "дана" (что в алгоритмической задаче означает "написана"), то она не может быть случайной - и правильно говорить не о вероятностях появления 0 и 1, а об их частоте.

Пусть дан генератор случайных значений. Например, мы бросаем монетку.

[Xaositect]

AndreyXYZ в сообщении #246836 писал(а):

Пусть дан генератор случайных значений. Например, мы бросаем монетку.

Иными словами, есть оракул(не обязательно рекурсивный), который по номеру $n$ выдает элемент последовательности $a_n$.

-- Вс сен 27, 2009 13:21:38 --

AndreyXYZ в сообщении #245276 писал(а):

Найти первое вхождение отрезка длины $n$, состоящего из одних единиц, в десятичной записи числа . Это задача является классической алгоритмически неразрешимой задачей, хотя для поиска её решения можно написать алгоритм.

Где Вы это прочитали? Это неверно.

AndreyXYZ в сообщении #246518 писал(а):

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

Задача называется алгоритмически неразрешиой, если существует алгоритм ее решения. А у этой задачи просто есть входы, для которых ответа принципиально не существует. А алгоритм на таких входах может зацикливаться.

-- Вс сен 27, 2009 13:23:46 --

Есть разница между двумя задачами:
1. Определить, существует ли в данной последовательности отрезок из $n$ единиц.
2. Определить первую цифру первого содержащегося в данной последовательности отрезка из $n$ единиц, если он существует.

Первая - алгоритмически неразрешима. Вторая - алгоритмически разрешима.

[Чудо-в-перьях]

hurtsy,Xaositect, все, я поняла.)