チューリング機械と計算機

Algorithms and Data Structures on C
チューリング機械と計算機
Algorithms and Data Structures on C
計算とは何か
• 計算するとは
– 入力を、ある決まりに従って変形し、出力すること
– y = f (x)
• x : 入力
• f : 決まり
• y : 出力
– 結果が出ない場合もありうる→計算不可能
• 計算の例：自然数の加算
– 1+1=2 , 1+2+3=6 , 1+1+3+2=7
入力
決まり
出力
●＋●
●●
●＋●●＋●●●
●●●●●●
●＋●＋●●●＋●●
●●●●●●●
Algorithms and Data Structures on C
チューリング機械
• Turing Machine
– Alan.M.Turingが1936年、「On computable numbers,
with an application to the entschidungsproblem（計算
可能数についてー決定問題への応用）」で発表
– 現在の計算機の基本的な動作は、チューリング機械の原
理と同等であるといえる。
• 計算機で原理上解ける問題＝チューリング機械で解ける問題
• 数学の形式体系はチューリング機械の動作に還元可能
• 計算機の不完全性の証明
– 停止問題（チューリング機械が停止するかどうかを判定するチュー
リング機械を作ることはできない）
Algorithms and Data Structures on C
チューリング機械の構造
• 以下の3つの構成要素
– 右側に無限に長いテープ（記憶装置）
– テープを読み書きするヘッド（入出力装置）
– 内部状態
• 以下の動作を停止するまで繰り返す
–
–
–
–
–
a
ヘッドの位置のテープを読む（#は空白）
ヘッドの位置に文字を書く
機械の内部状態Sを変える
ヘッドを移動する（左、右、そのまま）
プログラムにない場合は停止する
b
#
a
c
左移動 (L)
c
#
#
S
ヘッド
#
H
e
l
l
右移動 (R)
o
#
#
#
1
2
3
#
Algorithms and Data Structures on C
チューリング機械のプログラム
• 5つの文字の組
–
–
–
–
–
現在の状態S0
テープから読んだ入力I
テープに書き込む出力O
ヘッドの移動M
次の状態S1
状態によって動作が異なる
↓
変数の役割
↓
状況に応じた処理（if文）
S0
I
O
M
S1
0
0
0
R
0
0
1
1
R
1
1
0
0
R
0
1
1
1
R
2
2
0
0
R
0
2
1
0
L
2
2
#
#
R
0
Algorithms and Data Structures on C
2つの自然数の加算
•
どんな決まりが必要か？
1.
2.
3.
4.
5.
6.
7.
8.
テープの先頭から読む
＃（空白）が現れるまで右へ
＃が現れたら左へ
●を＃に変え左へ
＋が来るまで左へ。
その途中で先頭まで戻ったら、
●がなくなるまで右へ行き、最
後の＃を●に変えて終了
＋を●に変える
2.へ戻る
●●＋●●●＃＃＃＃
●●＋●●●＃＃＃＃
●●＋●●●＃＃＃＃
●●＋●●＃＃＃＃＃
●●＋●●＃＃＃＃＃
●●●●●＃＃＃＃＃
●●●●●＃＃＃＃＃
●●●●＃＃＃＃＃＃
●●●●＃＃＃＃＃＃
●●●●●＃＃＃＃＃
Algorithms and Data Structures on C
自然数の加算のプログラム
State0
Input
Output
Movement
State1
０
●
☆
Ｒ
１
０
＃
＃
Ｒ
０
１
●
●
Ｒ
１
１
＋
＋
Ｒ
１
１
＃
＃
Ｌ
２
２
●
＃
Ｌ
３
３
●
●
Ｌ
３
３
＋
●
Ｒ
１
３
☆
●
Ｒ
４
４
●
●
Ｒ
４
４
＃
●
Ｒ
５
ただし、＃は空白をあらわす。
Algorithms and Data Structures on C
自然数の加算の状態遷移
＃
1
0
●
数字を読んでいない
状態
数字を読んで右に移
動している状態
●、＋
＃
●
4
2
先頭まで戻って、右
に移動している状態
＃
＋
右端の空白を読んだ
状態
☆
●
5
終了した状態
3
最後の●を空白に置
き換えて左に戻って
いる状態
●
Algorithms and Data Structures on C
111→000問題
• テープ上に1が連続して3つ現れたら、それを0が3つ
の連続に置き換えよ。
S0
I
O
M
S1
0
0
0
1
0
0
1
1
1
1
1
0
0
1
0
1
1
1
1
2
2
0
0
1
0
2
1
0
-1
2
1
0
2
Algorithms and Data Structures on C
課題150930
• 前のページの111→000問題のチューリング機械の
プログラムの動作を、以下の要領で説明せよ。
– テープの初期状態が、
• 001110011011111000
の場合について、実行の順序に沿って説明せよ。
– 各状態は、どのような目的のために作られているかを、状
態遷移図を描いて説明せよ。
《提出要領》
• 作成方法：ワードで（ファイル名 scXXXXXX-al150930.docx）
• 提出方法：メールで
• 提出先：[email protected]
• メールタイトル：アルゴリズム課題150930 ←厳守！
• 提出期限：2015年10月4日（日）
• 警告：内容が酷似している2つ以上のレポートがあった場合は、双
方、不可になる可能性がある。
Algorithms and Data Structures on C
チューリング機械と計算機
終了
Algorithms and Data Structures on C
2つの自然数の加算（＃版）
•
どんな決まりが必要か？
1.
2.
3.
4.
5.
6.
7.
8.
テープの先頭から読む
＃（空白）が2つ連続するまで右
へ
＃が2つ連続したら2つ左へ
●を＃に変える
＃が来るまで左へ。
その途中で先頭まで戻ったら、
●がなくなるまで右へ行き、最
後の＃を●に変えて終了
＃を●に変える
3.へ戻る
●●＃●●●＃＃＃＃
●●＃●●●＃＃＃＃
●●＃●●●＃＃＃＃
●●＃●●＃＃＃＃＃
●●＃●●＃＃＃＃＃
●●●●●＃＃＃＃＃
●●●●●＃＃＃＃＃
●●●●＃＃＃＃＃＃
●●●●＃＃＃＃＃＃
●●●●●＃＃＃＃＃
Algorithms and Data Structures on C
自然数の加算（＃版）のプログラム
S0
I
O
M
S1
０
●
１
Ｒ
１
０
＃
＃
Ｒ
０
１
●
●
Ｒ
１
１
＃
＃
Ｒ
２
２
●
●
Ｒ
１
２
＃
＃
Ｌ
３
３
＃
＃
Ｌ
３
３
●
＃
Ｌ
４
４
●
●
Ｌ
４
４
＃
●
Ｒ
１
４
１
●
Ｒ
５
５
●
●
Ｒ
５
５
＃
●
Ｒ
６
ただし、＃は空白をあらわす。

Download Report