Изменения

Класс языков '''L''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной длиной ''n''.

Иначе говоряИнтерпретировать определение можно по-разному. Например, при рассмотрении машин Тьюринга входная лента используется лишь для чтения, языки должны быть разрешимы а размер рабочей ленты составляет ''O''(log ''n''). Или на ''RAM''-машинах, использующих конечное число используется ''O''(1) дополнительных переменных.

Обобщением класса '''L''' является класс '''[[Класс NL|NL]]''' — отличие состоит в использовании недетерминированной машины Тьюрингавместо детерминированной. РазумеетсяДетерминированная машина Тьюринга является частным случаем недетерминированной, что поэтому '''L''' ⊆ '''NL'''.