màquina de Turing

f
Matemàtiques

Màquina formada per una cinta il·limitada, dividida en cel·les, i per una capsa negra amb un cap lector.

Procedeix de la següent manera elemental. A cada cel·la de la cinta hom pot escriure un 0 o un 1. Aleshores, la màquina de Turing, segons l’estat intern de la capsa negra i del símbol que llegeix el cap lector, pot pendre una de les cinc decisions següents: 1, escriure un zero a la cel·la llegida pel cap lector, esborrant abans el que pugui haver-hi escrit; 2, escriure un 1 a la cel·la, esborrant abans el que pugui haver-hi escrit; 3, donar un pas cap a la dreta; 4, donar un pas cap a l’esquerra; 5, aturar-se. Una màquina de Turing és, doncs, una matriu com ara

Aquesta matriu actua de la forma següent. Si es troba en estat inter q 0 i el cap lector llegeix un 0, escriu un 1 i es manté en estat q 0 ; en canvi, si llegeix un 1, escriu un 1 i es col·loca en estat q 1 . Si es troba en estat q 1 i llegeix un 0, la cinta es desplaça una cel·la cap a la dreta i la màquina es col·loca en estat q 0 ; si llegeix un 1 es para, ja que es col·loca en un estat en el qual no pot actuar.