Pytania otagowane jako cellular-automata

4
Czy hałaśliwa wersja gry życia Conwaya obsługuje uniwersalne obliczenia?
Cytując Wikipedię , „[Gra życia Conwaya] ma moc uniwersalnej maszyny Turinga: to znaczy wszystko, co można obliczyć algorytmicznie, można obliczyć w ramach Gry życia Conwaya”. Czy takie wyniki obejmują hałaśliwe wersje Gry życia Conwaya? Najprostsza wersja jest taka, że ​​po każdej rundzie każda żywa komórka umiera z małym prawdopodobieństwem a …
3
Klasa języków rozpoznawalna przez 3-stanowe TM z pojedynczą taśmą
Przez pewien czas byłem ciekawy maszyn Turinga z dokładnie jedną taśmą i dokładnie 3 stanami (mianowicie stanem początkowym q0q0q_0, stan akceptacji i stan odrzucenia ). Zauważ, że zezwalam na dowolne (skończone) alfabety taśmowe (tzn. Alfabet na taśmie nie jest ograniczony do równego alfabetowi wejściowemu).qacceptqacceptq_{accept}qrejectqrejectq_{reject} Dla wygody zadzwoń do klasy języków …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.