1.古代における文化

アルゴリズムとチューリングマシン
「もの」(商品)としてのコンピュータ
「こと」(思想)としてのコンピュータ
アルゴリズム
Turing Machine
現実のコンピュータ
アルゴリズム



Algorithm (アルゴリズム)
Alkwarizmi(アルフワリズミ、アラブ)の創始
様々なアルゴリズム
– ユークリッドの互除法(最大公約数、最小公倍数)
– エラストテレスのふるい(素数)
– 探索
– ソート(整列)



バブルソート
クイックソート、ヒープソート etc.
一般的なアルゴリズム概念の成立は今世紀(コン
ピュータ誕生以降)
Turing Machine


Alan Turing (1912－1954)
「決定問題」
数学の全ての問題を1つずつ解決できる一
般的な機械的手続きは存在するか
(Hilbelt)


機械概念の定式化
「内部状態」の遷移
現実のコンピュータの仕組み
論理回路
順序回路
もしわれわれが、おそらく天使たちが持ち、人間の創
造主なら確実に持つような知識を人間について持って
いるとしたら､人間の本質についていまその定義にふ
くまれるものとは全く違う概念を持つはずである。あた
かもストラスブールの時計の内部にあるぜんまいや
歯車やその他の巧緻な品々すべて知っているものが
持つ知識は、単に針の動きを見、時計の時の打つの
を聴き、概観の若干にのみ瞠目してしまうような田舎
者が抱くものとは異なっているように…。ジョンロック
命題論理とブール代数

「命題」と、その「変数」のとり得る「値」
– 命題：「・・・は×××である」
– とり得る値：「真」か「偽」か（２値）。

命題Aに関しての真理値表
A 」A
ＴＦ
ＦＴ

２つの命題A,Bに関する演算（和、積）
A ＋ B, A ・ B
２つの命題A,Bに関する演算の
真理値表
A
B
A・B
A
B
A+B
T
T
T
T
T
T
T
F
F
T
F
T
F
T
F
F
T
T
F
F
F
F
F
F
基本論理ゲート

NOTゲート、

ORゲート、

ANDゲート
ブール代数の応用（回路の簡素
化）
ブール代数
」x+」y = 」( x・y) , 」x・」y = 」(x+y)
(ド・モルガンの定理)
回路の等価性
実際の回路

ダイオード回路

TTL（Transistor transit
logic）,ECL(emitter coupled logic)
NAND回路

デコーダとエンコーダ

エンコーダ：番号付けされたn個の入力のうちの1個が1､残りが0の
状態にあるとき、１の状態は何番目かを２進数で与える。

デコーダ：nビットの2進数が与えられると、それに対応する番号の出
力だけを１にする。
加算器
一桁の２進数の加算

a
0
0
1
1
b
0
1
0
1
carry
0
0
0
1
sum
0
1
1
0
sum:排他論理和
carry:論理積
半加算器と全加算器
半加算器：下の桁からの繰り上がりを勘定に入れない
全加算器：桁上がりも勘定に入れる
順序回路
•
•
•
1.フリップフロップ
2.有限状態機械
3.Turing 機械
記憶する回路
A
•
•
•
•
•
C
A 現在のC 次のC
0
0
0
0
1
1
1
0
1
1
1
0
もっともらしい記憶装置
(うまくいかない)
•
SRフリップフロップ
•
•
•
S入力:1、R入力:0
Q出力:1、」Q出力:0
(Rが0である限り、変わらない)
同期式SRフリップフロップ


C入力が０のときRまたはS入力が１になっ
ても出力には変化が無い。C入力はクロッ
クというものでパルス列が入る。
出力はこのパルスに同期する。
各種フリップフロップ
カウンタ(Tフリップフロップ)


入力されたパルスの数を2進化して出力
初段のフリップフロップの出力が2段目のク
ロック入力…。
状態遷移図

SRフリップフロップの状態遷移
有限状態機械(オートマトン)


自動販売機の「状態遷移」モデル
「記憶」のないチューリングマシン
Turingマシン
Turingマシンのテープ
一元数に１を加えるチューリ
ング機械
 00→00R
→11R
 10 →01STOP
 11 →11R
 01

動作確認はシミュレータソフトウェア(圧縮ファイルを解凍し、
`Readme.txt’ をお読みの上、使ってください)で行なえます。
万能チューリングマシン
テープに書かれたチューリングマシン
の「命令列」を読み取って、チューリン
グマシンの代わりを行う。
 後世のコンピュータの基本モデル。
 「コンピュータ」：プログラムがメモリに
内在され、自分でそれを買えることが
できるもの。

一元数を2倍にするチューリン
グ機械












00→00R
01 →10R
10 →101L
11 →11R
100 →110R
101 →1000R
110 →01STOP
111 →111R
1000 →1011L
1001 →1001R
1010 →101L
1011 →1011L
2つの一元数の最大公約数















00R → 00R
01 → 11L
10 → 101R
11 → 11L
100 → 10100R
101 → 110R
110 → 1000R
111 → 111R
1000 → 1000R
1001 → 1010R
1010 → 1110L
1011 → 1101L
1100 → 1100L
1101 → 11L
1110 → 1110L
1111 → 10001L
10000 → 10010L
10001 → 10001L
10010 → 100R
10011 → 11L
10100 → 00STOP
10101 → 10101R

Download Report