この記事はスタブです。

Feynman Lectures On Computation
Feynman Lectures On Computation Richard P. Feynman Anthony Hey

Westview Press 2000-07-07
売り上げランキング : 41586

Amazonで詳しく見る by G-Tools

    <p>
      <div id="toc_container" class="no_bullets">
        <p class="toc_title">
          Contents
        </p>

        <ul class="toc_list">
          <li>
            <a href="#1_Introduction_to_Computers"><span class="toc_number toc_depth_1">1</span> 1 Introduction to Computers</a><ul>
              <li>
                <a href="#12_Instruction_Sets"><span class="toc_number toc_depth_2">1.1</span> 1.2 Instruction Sets</a>
              </li>
            </ul>
          </li>

          <li>
            <a href="#2_Computer_Organization"><span class="toc_number toc_depth_1">2</span> 2 Computer Organization</a><ul>
              <li>
                <a href="#21_Gates_and_Combinational_Logic"><span class="toc_number toc_depth_2">2.1</span> 2.1 Gates and Combinational Logic</a>
              </li>
              <li>
                <a href="#23_More_on_Gates_Reversible_Gates"><span class="toc_number toc_depth_2">2.2</span> 2.3 More on Gates: Reversible Gates</a>
              </li>
            </ul>
          </li>

          <li>
            <a href="#3_The_Theory_of_Comptation"><span class="toc_number toc_depth_1">3</span> 3 The Theory of Comptation</a><ul>
              <li>
                <a href="#32_Finate_State_Machines"><span class="toc_number toc_depth_2">3.1</span> 3.2 Finate State Machines</a>
              </li>
              <li>
                <a href="#33_The_Limitations_of_Finite_State_Machines"><span class="toc_number toc_depth_2">3.2</span> 3.3 The Limitations of Finite State Machines</a>
              </li>
              <li>
                <a href="#34_Turing_Machines"><span class="toc_number toc_depth_2">3.3</span> 3.4 Turing Machines</a><ul>
                  <li>
                    <a href="#Problem_35"><span class="toc_number toc_depth_3">3.3.1</span> Problem 3.5</a>
                  </li>
                  <li>
                    <a href="#Problem_36"><span class="toc_number toc_depth_3">3.3.2</span> Problem 3.6</a>
                  </li>
                </ul>
              </li>
            </ul>
          </li>
        </ul>
      </div>
    </p>

    <p>
      <br clear="all" />
    </p>

    <h2>
      <span id="1_Introduction_to_Computers">1 Introduction to Computers</span>
    </h2>

    <h3>
      <span id="12_Instruction_Sets">1.2 Instruction Sets</span>
    </h3>

    <p>
      <strong>整数のべき乗の和の公式</strong><br />
    </p>

    <p>
      $$<br /> \begin{align}<br /> W_k(n-1)&#038;=1^k+2^k+\cdots+(n-1)^k\\<br /> &#038;=\frac{1}{k+1}\left( n^{k+1} + \begin{pmatrix} k+1\\1\end{pmatrix} B_1 n^k + \begin{pmatrix} k+1\\2\end{pmatrix} B_2 n^{k-1} + \cdots + \begin{pmatrix} k+1\\k\end{pmatrix} B_k n \right)<br /> \end{align}<br /> $$
    </p>

    <p>
      覚え方は<br /> $$<br /> \frac{1}{k+1}[(n+B)^{k+1} &#8211; B^{k+1}]<br /> $$<br /> に二項定理を適応してBの指数を下付きに直す。
    </p>

    <p>
      ここで、\(B_m\)はベルヌーイ数
    </p>

    <p>
      $$<br /> B_0 = 1, \quad \sum_{k=0}^n \begin{pmatrix}n+1 \\ k \end{pmatrix} B_k = 0 \quad (n = 1,2,3,\dots)<br /> $$
    </p>

    <p>
      こちらも覚え方は<br /> $$<br /> B^{n+1} = (1+B)^{n+1}<br /> $$<br /> に二項定理を適用し、Bの指数を下付きに直す。
    </p>

    <p>
      詳しくは松山 廣氏の<a href="http://www.sci.hyogo-u.ac.jp/matsuyam/lecture_note/maththin98.pdf">ベルヌーイ数のはなし</a>を見よ。
    </p>

    <h2>
      <span id="2_Computer_Organization">2 Computer Organization</span>
    </h2>

    <h3>
      <span id="21_Gates_and_Combinational_Logic">2.1 Gates and Combinational Logic</span>
    </h3>

    <p>
      半加算器(half adder)、全加算器(full adder)、r-bit の数字には(2r-1)個の半加算器が必要なことについてはWikipediaの<a href="http://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8">加算器</a>に書いてある。
    </p>

    <h3>
      <span id="23_More_on_Gates_Reversible_Gates">2.3 More on Gates: Reversible Gates</span>
    </h3>

    <blockquote>
      <p>
        p.37 CN gates can be connected up to make an exchange oprerator
      </p>
    </blockquote>

    <p>
      と書いてあるので、作ってみる。
    </p><figure id="attachment_7207" style="width: 252px" class="wp-caption alignleft">

    <a href="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/CN_gate.png"><img src="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/CN_gate.png" alt="CNゲート" title="CNゲート" width="252" height="120" class="size-full wp-image-7207" /></a><figcaption class="wp-caption-text">CNゲート</figcaption></figure> 

    <table>
      <caption>CNゲートの真偽表</caption> 

      <tr>
        <th>
          A
        </th>

        <th>
          B
        </th>

        <th>
          A&#8217;
        </th>

        <th>
          B&#8217;
        </th>
      </tr>

      <tr>
        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>
      </tr>

      <tr>
        <td>
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>
      </tr>

      <tr>
        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>
      </tr>

      <tr>
        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
        </td>
      </tr>
    </table>

    <p>
      以下のようにCNゲートを組むとexchange operatorが作れる。<figure id="attachment_7237" style="width: 486px" class="wp-caption alignleft"><a href="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/exchange_operatorCN_gates.png"><img src="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/exchange_operatorCN_gates.png" alt="exchange operator=CN gates" title="exchange operator=CN gates" width="486" height="304" class="size-full wp-image-7237" srcset="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/exchange_operatorCN_gates.png 486w, http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/exchange_operatorCN_gates-300x187.png 300w" sizes="(max-width: 486px) 100vw, 486px" /></a><figcaption class="wp-caption-text">exchange operator=CN gates</figcaption></figure>
    </p>

    <table>
      <caption>CNゲートを組み合わせて作ったexchange operatorの真偽表</caption> 

      <tr>
        <th>
          A<sub>1</sub>
        </th>

        <th>
          B<sub>1</sub>
        </th>

        <th>
          A<sub>2</sub>
        </th>

        <th>
          B<sub>2</sub>
        </th>

        <th>
          A<sub>3</sub>
        </th>

        <th>
          B<sub>3</sub>
        </th>

        <th>
          A<sub>4</sub>
        </th>

        <th>
          B<sub>4</sub>
        </th>
      </tr>

      <tr>
        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>

        <td>
        </td>
      </tr>

      <tr>
        <td>
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
        </td>
      </tr>

      <tr>
        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>
      </tr>

      <tr>
        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
        </td>

        <td>
          1
        </td>

        <td>
          1
        </td>
      </tr>
    </table>

    <h2>
      <span id="3_The_Theory_of_Comptation">3 The Theory of Comptation</span>
    </h2>

    <h3>
      <span id="32_Finate_State_Machines">3.2 Finate State Machines</span>
    </h3>

    <ul>
      <li>
        <a href="http://akita-nct.jp/yamamoto/lecture/2007/5E_info/11th/calmodel.pdf">計算のモデル化と可能性</a>
      </li>
    </ul>

    <p>
      Problem 3.2とProblem 3.3の答えが載ってる。図4の左側の1, 0に対する応答は1だと思う。
    </p>

    <h3>
      <span id="33_The_Limitations_of_Finite_State_Machines">3.3 The Limitations of Finite State Machines</span>
    </h3>

    <ul>
      <li>
        <a href="http://www.math.is.tohoku.ac.jp/~obata/lecture/2009-graduate/2009-in-6.pdf">ランダム・ウォーク</a>
      </li>
    </ul>

    <p>
      parenthesis checkerのところで、ランダムに開きカッコ、閉じカッコを並べたら、どのくらい閉じるのか、と思って調べた。
    </p>

    <p>
      <strong>Problem 3.4: Firing Squad problem</strong>
    </p>

    <ul>
      <li>
        <a href="http://hdl.handle.net/10487/1326"><原報>一斉射撃問題を解いてみる : 分かりやすい 8 状態最少時間解まで</a>
      </li>
      <li>
        <a href="http://motls.blogspot.com/2009/03/firing-squad-synchronization-problem.html">The Reference Frame: Firing squad synchronization problem</a>
      </li>
    </ul>

    <h3>
      <span id="34_Turing_Machines">3.4 Turing Machines</span>
    </h3>

    <ul>
      <li>
        <a href="http://morphett.info/turing/turing.html">Turing machine simulator</a>
      </li>
    </ul>

    <h4>
      <span id="Problem_35">Problem 3.5</span>
    </h4>

    <p>
      Unary multiplierを作る問題。<br /> eとbで区切られた以下のようなテープがあるとする。
    </p>

    <table class="tape">
      <tr>
        <td class="edge1">
          e
        </td>

        <td>
          1111&#8230;1
        </td>

        <td>
          b
        </td>

        <td>
          1111&#8230;11
        </td>

        <td class="edge2">
          e
        </td>
      </tr>

      <tr class="nottape">
        <td>
        </td>

        <td>
          m
        </td>

        <td>
        </td>

        <td>
          n
        </td>

        <td>
        </td>
      </tr>
    </table>

    <p>
      eとbの間にm個、bとeの間にn個の1があったときにeの後ろにmn個の1の列をつくるプログラムを作る。
    </p><figure id="attachment_7925" style="width: 404px" class="wp-caption aligncenter">

    <img src="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-5.png" alt="" title="problem3-5" width="404" height="175" class="size-full wp-image-7925" srcset="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-5.png 404w, http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-5-300x129.png 300w" sizes="(max-width: 404px) 100vw, 404px" /><figcaption class="wp-caption-text">Unary multiplierの状態図。数字は状態の番号を表す。</figcaption></figure> 

    <p>
      [text title=&#8221;Turing machine simulatorでUnaty multiplierを実現するプログラム&#8221;]<br /> :Initial inputの例: e111b1111e<br /> ; Machine syntax: <current state> <current symbol> <new symbol> <direction> <new state><br /> 0 1 0 r 1<br /> 0 b * r halt<br /> 0 * * r *<br /> 1 b * r 2<br /> 1 * * r *<br /> 2 1 x r 3<br /> 2 e * l 5<br /> 2 * * r *<br /> 3 _ y l 4<br /> 3 * * r *<br /> 4 x * r 2<br /> 4 * * l *<br /> 5 x 1 l *<br /> 5 0 * r 0<br /> 5 * * l *<br /> [/text]
    </p>

    <h4>
      <span id="Problem_36">Problem 3.6</span>
    </h4>

    <p>
      Binary addition。
    </p>

    <p>
      aとb、bとcに囲まれたバイナリ列を足す。桁は同じとする。<br /> 計算はcの後に逆順で記述、計算し終わったら順番を正しくする。
    </p><figure id="attachment_7941" style="width: 551px" class="wp-caption aligncenter">

    <img src="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-6.png" alt="" title="problem3-6" width="551" height="468" class="size-full wp-image-7941" srcset="http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-6.png 551w, http://sanrinsha.lolipop.jp/wp/wp-content/uploads/2011/05/problem3-6-300x254.png 300w" sizes="(max-width: 551px) 100vw, 551px" /><figcaption class="wp-caption-text">Binary additionの状態図</figcaption></figure> 

    <p>
      [text title=&#8221;Turing machine simulatorでBinary additionを実現するプログラム&#8221;]<br /> :Initial inputの例: a1111b1111c<br /> ; Machine syntax: <current state> <current symbol> <new symbol> <direction> <new state><br /> 0 b * l 1<br /> 0 * * r *<br /> 1 1 x r 2x<br /> 1 0 x r 2y<br /> 1 a _ r 6<br /> 1 * * l *<br /> 2x c * l 3x<br /> 2x * * r *<br /> 2y c * l 3y<br /> 2y * * r *<br /> 3x 1 x r 4x<br /> 3x 0 x r 4y<br /> 3x * * l *<br /> 3y 1 x r 4y<br /> 3y 0 x r 4z<br /> 3y * * l *<br /> 4x _ 0 r carry<br /> 4x y 1 r carry<br /> 4x * * r *<br /> 4y _ 1 l 5<br /> 4y y 0 r carry<br /> 4y * * r *<br /> 4z _ 0 l 5<br /> 4z y 1 l 5<br /> 4z * * r *<br /> carry _ y r 5<br /> 5 b * l 1<br /> 5 * * l *<br /> 6 c * r 7<br /> 6 * _ r * ;削除<br /> 7 1 x l 8x<br /> 7 y x l 8x<br /> 7 0 x l 8y<br /> 7 _ * r 10<br /> 7 * * r *<br /> 8x _ 1 r 9<br /> 8x * * l *<br /> 8y _ 0 r 9<br /> 8y * * l *<br /> 9 c * r 7<br /> 9 * * r *<br /> 10 1 * * halt<br /> 10 0 * * halt<br /> 10 * _ l *<br /> [/text]
    </p>

    <p>
      面倒なので他の問題は省略。
    </p>