Pytania otagowane jako turing-machines

Maszyna Turinga to podstawowy model obliczeń, szczególnie w pracy teoretycznej.

3
Jakim automatem jest Google Turing Doodle?
Z okazji urodzin Alana Turinga Google opublikował doodle przedstawiające maszynę. Jaką maszyną jest doodle? Czy może wyrażać język Turing Complete? Istnieją oczywiste różnice w stosunku do klasycznej maszyny Turinga: skończona taśma, ograniczenia w sposobie łączenia stanu, ... Doodle jest nadal dostępne tutaj (Wyświetlacz w prawym górnym rogu pokazuje oczekiwane wyjście.) …
5
Rozproszona maszyna Turinga?
Jestem studentem specjalizującym się w systemach rozproszonych, ale interesuję się również informatyką teoretyczną. Zastanawiałem się, czy istnieje formalna reprezentacja systemu rozproszonego na maszynie Turinga? To znaczy, czy można rozszerzyć (stworzyć wariant) koncepcję maszyny Turinga, aby skorzystać z przetwarzania rozproszonego? Jednym z pomysłów jest utworzenie wspólnej taśmy (coś podobnego do Tuple …
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 …
1
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść …
2
Maszyny Turinga, których zakończenie jest niemożliwe do udowodnienia?
Mam naiwne pytanie: czy istnieje maszyna Turinga, której zakończenie jest prawdziwe, ale której nie da się udowodnić żadną naturalną, spójną i skończoną aksjomatyczną teorią? Proszę o zwykły dowód istnienia, a nie o konkretny przykład. Może to mieć związek z analizą porządkową . Rzeczywiście, dla maszyny Turinga możemy zdefiniować jako najmniejszy …
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.