Un autómata linealmente acotado es una máquina de Turing cuya cinta está formada solamente por celdas de kn de largo, donde la longitud n es la secuencia de la entrada y k es una constante asociada al "autómata linealmente-acotado" particular, es decir la cantidad de cinta que el autómata permite usar se limita por un factor lineal k para que cuando entre una palabra de tamaño n (los símbolos de n) , la máquina determine si la palabra es aceptable, o si la palabra está en el lenguaje del autómata.