Maquina de Turing

Un article de Wikipèdia, l'enciclopèdia liura.
Fotografia d'un modèl raprochat d'una 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.

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[modificar | Modificar lo còdi]

Bibliografia[modificar | Modificar lo còdi]

Nòtas e referéncias[modificar | Modificar lo còdi]