Maquina de Turing

Una maquina de Turing es, en informatica abstracha, un modèl de foncionament d'un aparelh mecanic de calcul imaginat en 1936 per lo matematician britanic Alan Turing (1912-1954). Son objectiu èra de donar una definion precisa dau concèpte d'algoritme e de procedura mecanica. Es totjorn fòrça en informatica per formalizar la nocion de calcul e pausar un limit clar entre lei problemas calculables e lei problemas incalculables. Marquèt una etapa importanta dins l'aparicion dei premiereis ordinators.

Fotografia d'un modèl raprochat d'una maquina de Turing.

Es compausada de quatre elements :

• d'un riban infinit constituït casas consecutivas contenent lo simbòl d'un alfabet donat. Cada alfabet contèn un simbòl especiau dich « simbòl blanc » e d'autrei simbòls.
• un sistèma de lectura/escritura que permet de legir e escriure lei simbòls sus lo riban.
• un registre d'estat qu'enregistra l'estat actuau de la maquina. Lo nombre d'estats possibles es finit e existís un estat especiau, dich estat de començament que correspond a l'estat iniciau de la maquina avans sa mesa en foncionament.
• una taula d'accions qu'indica a la maquina lo simbòl d'escriure sus lo riban, la maniera de desplaçar lo sistèma de lectura, l'estat novèu (segon lo simbòl legit) e l'estat actuau de la maquina. S'i a ges d'accion per una combinason donada d'un simbòl legit e d'un estat, la maquina s'arrèsta.

Liames intèrnes

• Alan Turing.
• Informatica.
• Ordinator.

Bibliografia