Linear bounded automaton

From Esolang

Jump to: navigation, search

A linear bounded automaton (LBA) is a Turing machine that can, on its tape:

  • read a symbol
  • change a symbol
  • erase a symbol

but can't:

  • write a new symbol where there was none before.

(OK, that's a bit of a lie, but it gets the point across much better than a dry mathematical definition would. The truth is, it can write new symbols, but only up to a limit based on the number of symbols given on its initial tape, times a constant factor. Thus "linear bounded".)

Linear-bounded automata recognize the class of context-sensitive languages.

Retrieved from "http://esoteric.voxelperfect.net/wiki/Linear_bounded_automaton"
Personal tools