チューリング機械の状態遷移図

質問

h(x)=0(x=0のとき),定義されない(x>0のとき)

のチューリング機械の状態遷移図を書け

という問題なのですが、x>0のときというのが難しいです。
チューリング機械ではx≠0ということは指定できないですよね？
こういった場合はどのように書けばいいのでしょうか？
あと、「定義されない」ということなんですが最終的に空白なマスにとどまっていればいいのでしょうか？

回答No.2

Tacosan · ベストアンサー

#1 に補足:
まず「x=0」などの判断ですが, そもそも「入力をどのように与えるのか」が書かれていなければいかなる判断もできません. 確認してください. 常識的には「簡単に判断できる」ように与えるはずです.
で, 「定義されない」ということについても, チューリング機械の動作を使って定義しているはずです. 普通は #1 でいわれるように「当該関数を計算するチューリング機械が停止しない」ことをもって「関数値は定義されない」と定義します. ただし, これも「普通の定義」でしかないので, その問題に関して別の定義があったらそれに従うこと.

お礼

入力として(0,1)のような感じにすればいいということですよね。
納得できました。ありがとうございました。

回答No.1

stomachman

> チューリング機械ではx≠0ということは指定できないですよね？

どういう意味でしょ？
入力が0かどうかを判定することは、もちろん出来ますけど。

> あと、「定義されない」ということなんですが最終的に空白なマスにとどまっていればいいのでしょうか？

「定義されない」という表現の意味は、この文脈では「停止しない」ってことではないかな？

お礼

ありがとうございます。定義されない=停止しないで納得できました。ありがとうございます。