Örneğin, iki kelimenin birbirinin tersi olup olmadığını anlama problemi lineer zamanda çözülebilir:
- İlk adımda, Turing makinesi ilk kelimeyi okur ve o kelimeyi temsil eden bir duruma geçer
- İkinci bir geçişte, Turing makinesi diğer kelimeyi tersten okur
- İkinci okuma sonunda, geldiği durumun ilk durumla aynı olup olmadığına bakar
Dolayısıyla, eğer kelimenin uzunluğu ise, bu problem o kelime için adımda bitecek ve iki kelimenin birbirinin tersi olup olmadığını söyleyecektir.
Ayrıca bakınız: Logaritmik zaman, Üstel zaman, NP-complete