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

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

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




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

No.2 ベストアンサー 回答者： Tacosan 回答日時： 2009/07/31 11:17

#1 に補足:

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

この回答へのお礼

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

お礼日時：2009/08/04 21:02

No.1 回答者： stomachman 回答日時： 2009/07/31 02:16

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

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

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

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

この回答へのお礼

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

お礼日時：2009/08/04 21:01