Màquina de Turing simètrica
Una màquina de Turing simètrica és una màquina de Turing amb un graf de configuració que és indirecte (la configuració i porta a la configuració j si i només si j porta a i).[1][2]
Definició modifica
Formalment, es defineix una variant d'una màquina de Turing amb un conjunt de transicions de la forma (p,ab,D,cd,q) on p i q son estats, ab i cd son parells de símbols i D és la direcció. Si la direcció és esquerra, llavors el capçal de la màquina a l'estat p sobre un símbol b i precedit per un símbol a pot fer una transició movent el capçal cap a l'esquerra, canviant l'estat a q i reemplaçant els símbols ab per cd. La transició oposada (q,cd,-D,ab,p) es pot aplicar sempre. Si D és dreta la transició és anàloga. L'habilitat de comprovar dos símbols i canviar-los de cop no és essencial, però simplifica la definició.
Relació amb d'altres classes modifica
La classe de complexitat STIME(T(n)) és la classe de llenguatges que son acceptats per una màquina de Turing simètrica en temps O(T(n)). És senzill de provar que STIME(T) = NTIME (T) limitant el no-determinisme de les màquines a NTIME(T).
SSPACE(S(n)) és la classe dels llenguatges acceptats per una màquina de Turing simètrica funcionant en un espai O(S(n)) i SL = SSPACE(log(n)).
Vegeu també modifica
Referències modifica
- ↑ Papadimitriou, Christos H.; Lewis, Harry R. «Symmertric space-bounded computation (extended abstract)» (en anglès). ICALP 1980: International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 14-07-1980, pàg. 374–384. DOI: 10.1007/3-540-10003-2_85.
- ↑ Greenlaw, R.; Alvarez, C. «A compendium of problems complete for symmetric logarithmic space» (en anglès). computational complexity, 9, 2, 01-12-2000, pàg. 123–145. DOI: 10.1007/PL00001603. ISSN: 1420-8954.