En què difereix el problema d'acceptació dels autòmats acotats lineals del de les màquines de Turing?
Dijous, 03 Agost 2023 by Acadèmia EITCA
El problema d'acceptació dels autòmats lineals acotats (LBA) difereix del de les màquines de Turing (TM) en diversos aspectes clau. Per entendre aquestes diferències, és important tenir una comprensió sòlida tant dels LBA com dels TM, així com dels seus respectius problemes d'acceptació. Un autòmat acotat lineal és una versió restringida d'una màquina de Turing
- Publicat a Seguretat cibernètica, EITC/IS/CCTF Fonaments de la teoria de la complexitat computacional, Decidibilitat, Autòmats lligats lineals, Revisió de l'examen
Etiquetat sota: Problema d'acceptació, Seguretat cibernètica, Decidible, Problema d'aturada, AMLA, Màquina de Turing, INDECIDABLE
Una llengua pot ser alhora reconeixible i decidible de Turing? Per què o per què no?
Dijous, 03 Agost 2023 by Acadèmia EITCA
Una llengua pot ser reconeixible o decidible per Turing, però no pot ser totes dues. Això es deu a les diferències fonamentals entre aquests dos conceptes en el camp de la teoria de la complexitat computacional. Per entendre per què una llengua no pot ser alhora reconeixible i decidible per Turing, primer hem de definir què volen dir aquests termes. Una llengua