Co oznacza przestrzeń podliniowa dla maszyn Turinga?

Udowodniono, że problem decydowania, czy wejście jest palindromem, czy nie wymaga miejsca na maszynie Turinga. Jednak nawet przechowywanie danych wejściowych zajmuje miejsce więc czy to nie znaczy, że wszystkie maszyny Turinga wymagają miejsca ? $\Omega(\log n)$ $n$ $\Omega(n)$

Oczywiście nie ma tutaj sprzeczności, ponieważ każda funkcja, która wykorzystuje co najmniej przestrzeń liniową, również używa co najmniej przestrzeni logarytmicznej. Ale napisanie sugeruje, że maszyna Turinga może wykorzystywać mniej niż przestrzeń liniową - w końcu dlaczego ludzie spędzaliby tyle czasu na sprawdzaniu gdyby to było dokładnie to samo, co wydaje się być trywialny związany? Co to znaczy, że maszyna Turinga wykorzystuje mniej niż przestrzeń liniową? $\Omega(\log n)$ $\Omega(\log n)$ $\Omega(n)$

turing-machines space-complexity jsguy
źródło

Afaik, złożoność przestrzeni zwykle bierze pod uwagę dodatkową pamięć właśnie z tego powodu. (Zwróć uwagę, że twoje pytanie jest źle postawione; chcesz zapytać „jak osiągnąć O (log n) ...”).

Raphael

Odpowiedzi:

$O(\log n)$ $O(\log n)$

Yuval Filmus
źródło

Dziękuję za odpowiedź. Dlaczego musimy przekonwertować indeks na format binarny? Myślałem, że maszyny Turinga to abstrakcyjne modele obliczeń, więc dlaczego mieliby konwertować liczby dziesiętne na ich reprezentacje binarne?

jsguy

O (\log n)

$O(\log n)$

@DavidRicherby, czy komórka taśmy nie może zawierać numeru, który ma więcej niż jedną cyfrę?

jsguy

@jsguy Odśwież definicję maszyn Turinga. Komórka taśmy zawiera pojedynczy symbol z alfabetu.

David Richerby

@DavidRicherby, dzięki, myślę, że to ma dla mnie sens teraz!

jsguy