Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 19.10.2020
Сообщений: 11
1

Проблема применимости и проблема останова

07.01.2021, 11:02. Просмотров 603. Ответов 3


Привет! Как бы я не бился - никак не могу понять проблему останова и применимости алгоритмов в целом. Хочу попросить прям полное объяснение для чайника. Допустим вот я написал программу на паскале, определяющую остановится ли данная подпрограмма с данными исходными данными или нет:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
program problem;
 
type
    TFunction = function(k : integer) : boolean;
    ARR = array[1..100] of char;
var
    k : integer = 0;
 
function m(k : integer) : boolean;
begin
    if k > 100 then
        m := true
    else 
        while true do
end;
 
function P(m : TFunction; k : integer) : ARR;
begin
    if m(k) then
        P := 'остановилось'
    else
        P := 'не остановилось';
end;
 
begin
    readln(k);
    writeln(P(@m, k));
end.
Она может определить только остановилась ли подпрограмма. Конечно определить вошла ли она в цикл никак нельзя, ведь программа тупо зависнит. Проблема в том что остановится ли алгоритм я определил, то есть никакой проблемы я не увидел)) Либо я не понимаю самой формулировки проблемы, либо я чудо ученый, который решил неразрешимую проблему.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.01.2021, 11:02
Ответы с готовыми решениями:

VsCode и Rust проблема с точками останова
Всем привет. Начал изучать Rust, столкнулся с такой проблемой: в VsCode не срабатывают точки...

Проблема останова лжеца Гёделя и брадобрея Кантора
Наваял тут трактат о логике и основаниях математики. Расскажите, пожалуйста, в чём я не прав.

Проблема со скоростью интернета(проблема точно не в роутере и кабеле, а соответственно в пк)
Доброй ночи всем! Поздравляю всех с Новым годом! Но теперь я попрошу вас о помощи! Давно замечал,...

проблема при работе с китайским J-LINK 8 или же проблема с с
Всем привет. Решил Сам собрать себе дисковери кит на базе at91sam7s64-ek. Подарили мне китайский...

3
441 / 344 / 44
Регистрация: 20.09.2014
Сообщений: 2,131
08.01.2021, 10:43 2
Алгоритм неверный. По какому праву вы в else засунули код, который пишет на экране "не остановилось"? )))
0
589 / 403 / 107
Регистрация: 07.05.2013
Сообщений: 1,425
Записей в блоге: 1
08.01.2021, 10:59 3
Проблема останова заключается в том, что существуют такие алгоритмы, анализ которых не позволяет определенно сказать - завершится ли он или будет крутиться бесконечно.

Можно только запустить, сидеть и ждать...

Добавлено через 2 минуты
В Вашем примере все предельно ясно - при k <= 100 программа войдет в бесконечный цикл.

Добавлено через 5 минут
Простой пример - Гипотеза Коллатца:

https://ru.wikipedia.org/Гипотеза_Коллатца
0
292 / 256 / 74
Регистрация: 23.05.2016
Сообщений: 1,063
11.01.2021, 22:08 4
Цитата Сообщение от yyttyy Посмотреть сообщение
Конечно определить вошла ли она в цикл никак нельзя,
Ну если нельзя, то ваш алгоритм не годится для разрешения проблемы останова.

А вообще на вход вашему анализатору P нужно подать текст (код) функции m и значение параметра k. Если анализатор сможет выдавать правильный ответ вида "завершится" / "не завершится" для любых функций m и любых значений параметра, то только тогда можно сказать, что проблема останова вами решена. Но такой анализатор написать невозможно.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.01.2021, 22:08

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

Проблема с Linux Mint 20(А может и не проблема)
Когда нажимаю на sk Hynix появляется это окошко(так должно быть или нет)?

Выдает ошибку, а я не могу понять в чем проблема. В чем проблема, скажите пожалуйста!
dx=0.0005; epsillon=0.00002; i=0; for x= 0:0.0005:3 i=i+1; if x&lt;1 y (i)=-1; ...

Холодильник LG .мод GR-M392YQ.Проблема с дверю, Проблема с дверю при закрывании
Доброго времени суток уважаемые! Холодильник LG GR-M392YQ с первых дней клиент жалуется на то что...

Применимости Spring и EJB
Где сейчас используют Spring? Может ли он стать заменой EJB или наоборот? Чем занимаетесь на...

Условия применимости признака Даламбера
Вот у меня имеется такой вопрос: К каким рядам можно применять признак Даламбера ? Я сначала...

Сокращение булевой функции. Делема о применимости формулы
Могу ли я воспользоваться свойством: -(A v B) = -A-B Для упрощения функции: -(A v B v C) И...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.