La decidibilità è un concetto fondamentale nel campo della teoria della complessità computazionale, in particolare nel contesto degli automi limitati lineari (LBA). Per comprendere la decidibilità, è importante avere una chiara comprensione degli LBA e delle loro capacità. Un automa limitato lineare è un modello computazionale che opera su un nastro di input, che è