Имеется машина Тьюринга с входным алфавитом Σ и ленточным алфавитом Γ.Алфавит Σ не содержит пустой символ, Γ содержит.Давайте представим пустой символ как _.Скажем, эта машина Тьюринга, получив вход w , записывает как вывод w _ w .То есть вывод является повторением ввода с пустым символом в середине.
Отбрасывается ли пустой символ при рассмотрении вывода?Должны ли мы считать вывод ww , несмотря на то, что w_w записано на ленте?В случае, если пустой символ отбрасывается: это так, потому что он не принадлежит Σ или потому что пустой символ всегда отбрасывается?