Bir sonlu durum makinesinin durması garanti edilen bir terim var mı?

Question

Bir durum makinesi hakkında daha önce bir tartışma başlatıyordum ve bazı girişlerde durup durmayacağı sorusu vardı. Önemli ve sıkça dile getirilen devlet makinelerinin bir özelliği gibi görünüyor, ama hayatımın isminin ne olduğunu anlayamıyorum. Böyle bir terim var mı? "Ölümcül", "sonsuza kadar döngü dışı" mı yoksa başka bir şey mi?

Answer 1

Her zaman duran bir makineye decider adı verilir.

Bir karar gereği, yalnızca tüm girişleri durduran bir makine olması gerekir. Örneğin, tüm DFA'lar, DPDA’lar gibi, kararlıdır.

Answer 2

Tahmin ettiğim soruya benzeyen ünlü "halting problem"'dan türetilen "durma", yani belirli bir girişte durup durmayacağı. Önemli bir husus, bir makinenin genel olarak "durması" olarak değil, belirli bir girdi olarak tanımlanmasıdır. Genel durumun çözümsüz olduğu kanıtlanmıştır (Turing tarafından).