1. ホーム
  2. theory

[解決済み] チューリングコンプリートとは?

2022-03-16 21:21:36

質問

チューリングコンプリートとはどういう意味ですか?

理論的なことはあまり考えずに、簡単に説明してください。

どのように解決するのですか?

以下、簡単に説明します。

チューリング完全システムとは、(実行時間やメモリに関する保証はないものの)答えを見つけるプログラムを書くことができるシステムのことです。

つまり、誰かが「私の新しいものはチューリング・コンプリートだ」と言ったとしたら、それは原理的には(実際にはそうでないことも多いのですが)どんな計算問題も解決するのに使えるということなのです。

たまに冗談で...ある人はviでチューリングマシーンのシミュレーターを書いたので、viは世界で唯一必要とされる計算エンジンだと言うことも可能です。