Tenint en compte els PDA no deterministes, la superposició d'estats és possible per definició. Tanmateix, els PDA no deterministes només tenen una pila que no pot estar en diversos estats simultàniament. Com és possible això?
Per abordar la qüestió sobre els autòmats pushdown no deterministes (PDA) i l'aparent paradoxa de la superposició d'estats amb una sola pila, és essencial tenir en compte els principis fonamentals del no determinisme i la mecànica operativa dels PDA. Un autòmat pushdown és un model computacional que amplia les capacitats dels autòmats finits incorporant un emmagatzematge auxiliar.
- Publicat a Seguretat cibernètica, EITC/IS/CCTF Fonaments de la teoria de la complexitat computacional, Pumba automàtics, Equivalència de CFG i PDA
Com representa una màquina de Turing no determinista múltiples transicions per a un estat i un símbol d'entrada determinats?
Una màquina de Turing no determinista (NTM) és un model teòric de càlcul que permet múltiples transicions possibles des d'un estat i símbol d'entrada determinats. Aquest concepte de no determinisme és un aspecte fonamental de la teoria de la complexitat computacional i juga un paper important en la comprensió de les capacitats i limitacions de les màquines de Turing. En una màquina de Turing no determinista,