Es pot limitar una cinta a la mida de l'entrada (que equival a que el capçal de la màquina de tornejat estigui limitat per moure's més enllà de l'entrada de la cinta TM)?
Dissabte, maig 25 2024
by Emmanuel Udofia
La qüestió de si una cinta es pot limitar a la mida de l'entrada, la qual cosa equival a que el cap d'una màquina de Turing no es mou més enllà de l'entrada de la cinta, s'endinsa en l'àmbit dels models computacionals i les seves limitacions. Concretament, aquesta pregunta toca els conceptes de delimitat lineal
Posa un exemple d'un problema que es pot decidir amb un autòmat lineal acotat.
Dijous, 03 Agost 2023
by Acadèmia EITCA
Un autòmat lineal acotat (LBA) és un model computacional que funciona en una cinta d'entrada i utilitza una quantitat finita de memòria per processar l'entrada. És una versió restringida d'una màquina de Turing, on el capçal de la cinta només es pot moure dins d'un rang limitat. En l'àmbit de la ciberseguretat i la teoria de la complexitat computacional,