回答編集履歴
2
有限かどうかは怪しいので消す
answer
CHANGED
|
@@ -8,8 +8,8 @@
|
|
|
8
8
|
Wikipediaを読んで理解できればいいのですが、難しいようであればオートマトンを基礎から勉強していくとそのうちチューリングマシンにたどり着くと思います。
|
|
9
9
|
|
|
10
10
|
直感的には、
|
|
11
|
-
- データ（どれほど膨大であってもいい
|
|
11
|
+
- データ（どれほど膨大であってもいい）がある
|
|
12
|
-
- データを処理するルール（どれほど膨大で複雑であってもいい
|
|
12
|
+
- データを処理するルール（どれほど膨大で複雑であってもいいが、ちゃんと形式的に定義できて矛盾しないもの）がある
|
|
13
13
|
- ルールに則ってデータを処理する
|
|
14
14
|
|
|
15
15
|
みたいなことができればチューリング完全です。ただし「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束になっています（と思います）。
|
1
修正
answer
CHANGED
|
@@ -8,8 +8,8 @@
|
|
|
8
8
|
Wikipediaを読んで理解できればいいのですが、難しいようであればオートマトンを基礎から勉強していくとそのうちチューリングマシンにたどり着くと思います。
|
|
9
9
|
|
|
10
10
|
直感的には、
|
|
11
|
-
- データ（どれほど膨大であってもいい）がある
|
|
11
|
+
- データ（どれほど膨大であってもいい（ただし有限））がある
|
|
12
|
-
- データを処理するルール（どれほど膨大で複雑であってもいいが、ちゃんと形式的に定義できて矛盾しないもの）がある
|
|
12
|
+
- データを処理するルール（どれほど膨大で複雑であってもいい（ただし有限）が、ちゃんと形式的に定義できて矛盾しないもの）がある
|
|
13
13
|
- ルールに則ってデータを処理する
|
|
14
14
|
|
|
15
15
|
みたいなことができればチューリング完全です。ただし「メモリに乗り切らない計算はできないのでチューリング完全ではないね」とは言わないお約束になっています（と思います）。
|