Soru: n ≥ 1 olmak üzere

işlemini gerçekleştiren Turing makinasını tasarlayın. Biçimsel tanımını verin.

Çözüm:

1- Önce 0 yerine T koyulur.

2- Sağdaki 1 ler T nin solundaki B lerin yerine taşınır. 1 sayısı kadar 2 T lerin soluna eklenir.

3- 1 lerin 2 katı alınıp tekrar eski yere getirilir. (2 katı alınıdığı zaman sonuç sağa kayıyor. Bunun için sola öteleme yapıyoruz.)

 4. 1. adıma dönülür taki 0 lar bitene kadar. En sonunda 1 tane 2 eklenir.