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.