- ベストアンサー
チューリングマシンについての問題。
人からこのような問題を聞かれましたが、全く意味がわからず困っています。 無限にテープ上に、英小文字が適当に並んでいる。 現在チューリングマシンが読んでいるところから右側にある、sinという文字列を見つけたら、cosと書き換えたい。 この問題を解くための、チューリングマシンの規則を設計しなさい。（最小限） 規則を設計・・・って解答例としてどういう解答が考えられるのでしょうか？
- usui323
- お礼率84% (351/415)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数5
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
1:(s) _R2, (not s) _R1 というのは、「状態1」の記述で、 「文字がsならば_R2の動作を行い、 s以外ならば_R1の動作を行う」 というつもりで書いています。 いろいろ記号はあると思いますが、 手元にあった本を参考にして、似た書き方を使っています。 いま思いつきましたが、1回書き換えるだけならば 1:(s) _R2, (not s) _R1 2:(i) _R3, (not i) _R6 3:(n) sL4, (not n) _R6 4: oL5 5: c(停止) 6: _L1 でもいいかもしれません。
その他の回答 (1)
- liar_adan
- ベストアンサー率48% (730/1515)
なんだか課題のような気もしますが…面白そうなので答えます。 以下のような感じでどうでしょう。 「cR6」は「cを書き込んで右に行って状態6に遷移」の意味です。 「_L4」は「何も書かず左に行って状態4に遷移」です。 一度書き換えを行ったら停止するようにしています。 1:(s) _R2, (not s) _R1 2:(i) _R3, (not i) _R8 3:(n) _L4, (not n) _R8 4: _L5 5: cR6 6: oR7 7: s(停止) 8: _L1 また 1:(s) _R2, (not s) _R1 2:(i) _R3, (not i) _L8 3:(n) _L4, (not n) _L8 4: _L5 5: cR6 6: oR7 7: s(停止) 8: _R1 でもいいでしょう。たぶん。
お礼
解答ありがとうございます。 解答なしだろうと思っていたので、非常にうれしいです。 こういう問題ってこのような解答の仕方をするものなのでしょうか？ 1:(s) _R2, (not s) _R1 というのはどういう意味なのでしょうか？ ちょっと、このような書き方をはじめて見ましたので。 私はチューリングマシンの話なんかも全然知らないんですけどね(^_^;)
関連するQ&A
- チューリングマシンの状態数について
この質問で言うチューリングマシンは、 「使用できる文字が0,1,Xだけのもの」とします。 自然数nに対し、 「空列を入力して動作を開始すると、有限ステップで停止して、停止したときにテープに書き残されている文字数がn以上」 であるようなチューリングマシンを全て集めた集合をKnとします。 そして、 g(n)= min{size(M) | M∈Kn } とします。ただし、size(M)はチューリングマシンMの状態数であり、minは「最小値」を意味します。 各nに対してKnは非空集合なので、g(n)の値はどんなnに対しても一意に定義されます。 すなわち、gは自然数上の全域関数です。 ビジービーバー関数は「状態数」から「その状態数のチューリングマシンが書き残せる最大字数」を求めるものでありますが、 この関数gは「字数」から「それ以上の字数を書き残せるチューリングマシンの最小状態数」を求めるものです。 このgが計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。 よろしくお願いいたします。 ((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)
- ベストアンサー
- C・C++・C#
- 無限積分の問題
次の問題の解き方を教えてください。 【問題】 ＋∞ ∫{1/(1+x^2)}dx を求めよ －∞ 次のように解答を進めました -------------------------------------------------------------------- 【解答】 まず、∫{1/(1+x^2)}dxについて考える。 x=tanθとおくと、 dx/dθ=1/cos^2θ から、 dx=dθ/cos^2θである。 1+x^2=1+ tan^2θ=1+sin^2θ/cos^2θ = 1/cos^2θ よって、1/(1+x^2)=cos^2θ したがって、∫{1/(1+x^2)}dx は、∫cos^2θ*(dθ/cos^2θ)=θ+c=tan^-1x+C ------------------------------------------------------------------- このようになりました。 しかし、この後、どう無限積分につなげていき、解くべきかわかりません。 cos^2θを、無限積分で解くという形になるのでしょうか。 しかし、例えそうだったとしても、解答がどうなるのかわかりません。 コサインの無限積分は収束して確かに存在する・・・・・・ジャイロ・ツェペリの黄金回転でしょうか？ どなたか、何卒お力添えください。 ニョホホホ。
- ベストアンサー
- 数学・算数
- この問題の解き方を教えてください><
この問題の解き方を教えてください>< 0≦θ≦2πのとき次の関数の最大値と最小値、およびそのときのθの値を求めよ (1)y=sinθcosθ (2)y=sinθ－cosθ (3)y=－sinθ＋√3cosθ－1 (4)y=sinθsin(θ＋2/3π) 1つでもいいので、よろしくお願いします><
- ベストアンサー
- 数学・算数
- 三角関数の合成と最小値について
『0°≦θ≦90°のとき、sinθ+√3cosθの最小値を求めよ』という問題が分からないでいます。 以下に途中までの考え方を書きます。（解答は1です） sinθ+cosθを合成して文字を1種類にすると、 (与式)=2sin(θ+π/3) 0°≦θ≦90°は0≦sinθ≦1だから、不等式は 0≦2sin(θ+π/3)≦1 0≦sin(θ+π/3)≦1/2 θ+π/3=tとおくと、 0≦sint≦1/2 0°≦θ≦90°は0≦θ≦1/2πだから、、 0≦sin(θ+π/3)≦1/2π π/3≦θ+π/3≦(1/2+1/3)π π/3≦θ+π/3≦5/6π ここまでは考えつき、次にtの範囲を調べれば良さそうなのはなんとなく想像はつくのですが、具体的にどう続きを持っていけば良いのか困っています。 ご回答どうぞよろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 三角関数の相互関係[証明問題]
tanθ=２－√３のとき、sinθ、cosθの値を求めなさい。 解答 cosθ＝（√６＋√２）／４ sinθ＝（√６ー√２）／４ cosθは求まりました。sinθが解答通りの答えになりません。数研出版の問題集やっているんですがこの解答合っているでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- 三角関数で問題の解答の意味がわからないですよ
問題なんですが、 tanΘ＝tのとき、 1-t^2 cos=-------- 1+t^2 であることを示せ。 その解答が cos^2Θ-sin^2Θ cos2Θ = cos^2Θ-sin^2Θ = -------------- cos^2Θ+sin^2Θ 1-tan^2Θ 1-t^2 = ------------- = -------- 1+tan^2Θ 1+t^2 この解答で、 cos^2Θ-sin^2Θの跡に、なぜ cos^2Θ-sin^2Θ --------------- cos^2Θ+sin^2Θ がでてくるのかがさっぱりわかりません。 アドバイスよろしくお願いします・・・・
- ベストアンサー
- 数学・算数
- 三角関数の問題について
数学の問題です。解ける方よろしくお願いします f(θ)=sin3θ-cos3θ+3sin2θ-9(sinθ+cosθ) ただし0<=θ<2π (1)t=sinθ+cosθとおくとき,f(θ)をtで表しなさい (2)f(θ)の最大値と最小値、およびそのときのθの値を求めなさい よろしくお願いします・・・！
- ベストアンサー
- 数学・算数
お礼
解答ありがとうございました。 意味がわかりました。 なるほど、こういう風に書くこともできるのですね。 C言語などでプログラムしろといわれれば簡単ですが、 設計しなさいとはどう書いて良いのかわかりませんでした。 大変参考になりました。 親切な解答ありがとうございました。