Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie.
Podobne drzewa można również skonstruować do wizualizacji obliczeń maszyn probabilistycznych i kwantowych. (Należy zauważyć, że dla niektórych celów lepiej jest nie wyświetlać powiązanego wykresu dla obliczeń kwantowych jako drzewa, ponieważ dwa węzły reprezentujące identyczne konfiguracje na tym samym poziomie drzewa mogą się wzajemnie „anulować” z powodu interferencji kwantowej, ale to nie ma nic wspólnego z obecnym pytaniem).
Oczywiście obliczenia deterministyczne nie są takie; istnieje jedna „gałąź” w odpowiednim „drzewie” dla dowolnego uruchomienia maszyny deterministycznej.
We wszystkich trzech wspomnianych wyżej przypadkach czasem, co sprawia, że obliczenia te są „trudne” dla komputerów deterministycznych, nie jest tak naprawdę rozgałęzieniem, a raczej kwestią ilości rozgałęzień w drzewie. Na przykład niedeterministyczna maszyna Turinga w czasie wielomianowym, która gwarantuje wytwarzanie drzew obliczeniowych, których „szerokości” (tj. Liczba węzłów na najbardziej zatłoczonym poziomie) są również ograniczone przez funkcję wielomianową wielkości wejściowej, mogą być symulowane przez wielomian -deterministyczna TM. (Zauważ, że ten warunek „wielomianowej szerokości” jest równoważny z ograniczeniem NTM do uzyskania co najwyżej logarytmicznie ograniczonej liczby niedeterministycznych domysłów.) To samo jest prawdą, kiedy kładziemy podobne granice szerokości na obliczeniach probabilistycznych i kwantowych.
Wiem, że zagadnienie to zostało szczegółowo zbadane w obliczeniach niedeterministycznych. Zobacz na przykład ankietę „ Ograniczony niedeterminizm ” przeprowadzoną przez Goldsmitha, Levy'ego i Mundhenka. Moje pytanie brzmi: czy to zjawisko „ograniczonego rozgałęzienia” lub „ograniczonej szerokości” zostało zbadane we wspólnej strukturze obejmującej wszystkie modele niedeterministyczne, probabilistyczne i kwantowe? Jeśli tak, jaka jest jego standardowa nazwa? Wszelkie linki do zasobów będą mile widziane.