halting problem

halting problem (tsz. halting problems)

1. (informatika) megállási probléma

A halting problem a számítástudomány és a matematikai logika egyik legfontosabb és legismertebb nem eldönthető problémája. 1936-ban Alan Turing mutatta meg, hogy ez a probléma általánosan nem oldható meg algoritmikusan – ez volt az első formális bizonyíték a nem számíthatóságra.

Adott egy program (Turing-gép) és egy bemenet – el tudjuk-e dönteni, hogy a program megáll-e azon a bemeneten, vagy örökké fut?

Formálisan:

• Legyen ${\textstyle P}$ egy program, és ${\textstyle x}$ egy bemenet.
• Kérdés: Megáll-e ${\textstyle P}$ a ${\textstyle x}$ bemeneten?

• A halting problem az első formális példa egy nem eldönthető problémára.
• Ez korlátokat szab annak, hogy mit tudunk automatizálni.
• Minden más nem eldönthetőség (pl. Rice-tétel) visszavezethető a halting problemre.

Tegyük fel, hogy létezik egy gép ${\textstyle H}$, amely megoldja a halting problem-et:

def H(program_code, input_code):
    """Előfeltétel: eldönti, hogy a program megáll-e a bemenetre"""
    return True or False

Most építünk egy új programot:

def D(code):
    if H(code, code):  # Ha megáll önmagára...
        while True:    # ... akkor fuss örökké!
            pass
    else:
        return          # Egyébként megáll

• Ha H(D, D) == True, akkor D örökké fut → ellentmondás
• Ha H(D, D) == False, akkor D megáll → ellentmondás

👉 Paradoxon: ${\textstyle D(D)}$ megáll, ha és csak ha nem áll meg → ellentmondás

Következtetés: nem létezhet ilyen ${\textstyle H}$, tehát a halting problem nem eldönthető.

• Nem létezik általános algoritmus, amely minden bemenet esetén megmondja, hogy egy program leáll-e.
• Ez vonatkozik minden Turing-teljes nyelvre: Python, C, Java, stb.
• Bármely nemtriviális programviselkedés eldöntése általában szintén lehetetlen → lásd: Rice-tétel

• A fordítók nem tudják mindig megmondani, hogy egy ciklus végtelen-e.
• Static analysis eszközök csak bizonyos eseteket fednek le.
• A biztonsági elemzés, verifikáció csak részleges lehet automatizálva.

• halting problem - Szótár.net (en-hu)
• halting problem - Sztaki (en-hu)
• halting problem - Merriam–Webster
• halting problem - Cambridge
• halting problem - WordNet
• halting problem - Яндекс (en-ru)
• halting problem - Google (en-hu)
• halting problem - Wikidata
• halting problem - Wikipédia (angol)