「無限ループの状態」そのものをIF文の条件にはできないのか？

前提・実現したいこと

素朴な疑問なんですが、無限ループを処理する方法は「処理時間が〇〇秒を越した時にbreak」以外に存在しますか?

Pythonを使って、ある問題でwhileの無限ループの処理を「処理時間が10秒を超えたらbreak」を再現するために以下のような条件付をして回しました。
ただ、自分としては「無限である」ということそのものを条件にしたいです。10秒に特に根拠がないからです。

数学に詳しくないのでよくわからないのですが、「無限であること」を再現して、その条件から外れるとループ処理から外せることはできますか？

該当のソースコード

処理時間が10秒超えたらbreak

python
1import time
2
3start = time.time()
4while time.time() - start <= 10:
5    処理内容
6

Zuishin

2020/05/02 07:46 編集

自分で作るコードなら、無限かどうか自分でわかると思います。終了条件を満たせる可能性が無いなら無限です。また、たとえ有限だとしても、処理に極めて長い時間がかかるなら終了させた方が良いと思います。

退会済みユーザー

2020/05/02 07:46

それはどこで判断しますか？　時間だけですか？

Zuishin

2020/05/02 07:47

時間ではなく論理で判断できると思いますが、実際どのような処理を想定していますか？

退会済みユーザー

2020/05/02 07:54 編集

ある文字列が与えられて、その要素である一文字全てがあるルールに則って変化します。何回かのループの後、その文字列が、最初の文字列と同じになったらループから外れます。同じにならなければ＝無限ループであれば、同じにならないと出力します。

Zuishin

2020/05/02 07:56

同じになる可能性が無ければ無限です。あるなら有限です。それ以上は具体的な条件がわからないので言えません。

Zuishin

2020/05/02 07:59

たとえばある文字 abc が与えられ、最初の一文字 a が a から z までの値を順に取るなら、これは有限です。しかし b から z の値を取るなら、これは無限です。

quickquip

2020/05/02 08:10

https://ja.stackoverflow.com/questions/66202/ 以下のヘルプを参考に。 https://teratail.com/help#posted-otherservice 「解決した際には必ずteratail及びすべての投稿に解決した旨と、どのように解決したかを記載してください」を滞りなく実行してください。

行動規範の内容に同意します

回答4件

ベストアンサー

「無限である」ということそのものを条件にしたいです。

「あるコードが無限ループになるか」を、どんなコードでも有限時間内に正しく判定する方法は、存在しないことが証明されています。

理論計算機科学で「停止性問題」と呼ばれる問題です。

投稿2020/05/02 07:58

maisumakun

総合スコア146018

退会済みユーザー

2020/05/02 08:13

ありがとうございます。停止性問題という言葉を初めて知りました面白いですということは、無限かどうかを判断するには、やはり時間で考えるしかないということですか？

maisumakun

2020/05/02 08:21

> 無限かどうかを判断するには、やはり時間で考えるしかないということですか？コードの動きを人間が考えて結論づけることは、（普通のプログラムの場合）たいてい可能です。

退会済みユーザー

2020/05/02 08:23

すいません。どういう意味ですか？

maisumakun

2020/05/02 08:28

書いてのとおりです。機械的な判定は不可能ですが、人間がコードを追いかけて、どのような動作をするか分析するという手段がある、ということです。（もっとも、理論計算機科学の分野でなければ、無限ループしうるプログラムを実用する場面は「メッセージループなど、永久に繰り返すことを意図して無限ループさせている」あるいは「数値解析など、処理が進んでみないときちんと終わるかわからない」ものなので、分析する必要は通常生じません）

maisumakun

2020/05/02 08:32

https://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC 「停止しないと信じられているが、停止しないことの証明がいまだ得られていない」ようなプログラムも、研究の世界では存在するようです。

退会済みユーザー

2020/05/02 08:45

丁寧にありがとうございます。勉強してきます

行動規範の内容に同意します

時間でなくループ回数で判定してみては如何でしょう。
その処理のループ回数の最大を見積もることができることが必要ですが。

ここでは 2 つのループで回している処理があります。
最初のループは 10 秒かかりますが、処理は終了します。
次のループは、break 判定が間違っているので break が実行されうることがありません。
でもループ実行回数が想定されるループ回数より多いので変だと感知しています。

p.py

python3
1import time
2
3MAX_LOOP_COUNT = 100
4
5# 処理時間がかかるが, 想定される最大ループ回数m中で処理が終わる
6# 1 .. 10 までの合計を求める
7sum = 0
8i = 1
9loop_count = 0
10
11while loop_count < MAX_LOOP_COUNT:
12    print(".", flush=True, end="")
13    time.sleep(1)
14    sum += i
15    i += 1
16    if i >= 10:
17        break
18    loop_count += 1
19
20if loop_count >= MAX_LOOP_COUNT:
21    print("\n無限ループの可能性があるので、処理を中断しました。")
22else:
23    print("\nsum=", sum)
24    
25# break 条件が間違っているので無限ループになってしまう処理だが、
26# それを検知している。
27sum = 0
28i = 1
29loop_count = 0
30while loop_count < MAX_LOOP_COUNT:
31    print(".", flush=True, end="")
32    time.sleep(0.01)    
33    sum += i
34    i += 1
35    if i < 0:  # <--  条件が間違っている
36        break
37    loop_count += 1
38
39if loop_count >= MAX_LOOP_COUNT:
40    print("\n無限ループの可能性があるので、処理を中断しました。")
41else:
42    print("\nsum=", sum)
43