یک ‎«ماشین تورینگ یک‌بارنوشتنی‎» یک ماشین تورینگ است با یک نوار که هر خانه‌ی آن (شامل بخشی از نوار که ورودی روی آن قرار گرفته) را حداکثر یک بار می‌توان تغییر داد. به طریق مشابه، خانه‌های یک ‎«ماشین تورینگ دوبار نوشتنی‎» را حداکثر دو بار می‌توان تغییر داد.

1. نشان دهید ماشین تورینگ دوبار نوشتنی با مدل معمولی ماشین تورینگ هم‌ارز است.
2. نشان دهید ماشین تورینگ یک‌بار نوشتنی با مدل معمولی ماشین تورینگ هم‌ارز است.

• سوال بعد
• سوال قبل