2013年8月1日木曜日

SQLはチューリング完全なんだけど…

Wikipediaでチューリング完全について調べると、
SQLはチューリング完全ではないという一文が見つかります。

しかしこれは誤記だと言われていて、
SQLでBrainf*ckを実装することで証明した事例を見つけることができます。

ん~、ではなんで間違えたのでしょうか。

当てずっぽうの推理ですけど、
ストアドプロシージャ無しではチューリング完全ではないって話でしょうか。

つまりチューリング完全ではないと書いた人は、
「DMLの範囲ではチューリング完全ではないよね」って言いたかったのではないでしょうか。

先に言っておきますと、
ストアドプロシージャは1996年に標準規格へ盛り込まれているそうです。

よって標準規格ではないというツッコミは(多分)使えません。

なのでDMLの範囲ではと補足すれば正しくなるのでしょうか?

それともDMLの範囲でも再帰的な書き方ができて、
チューリング完全にできるのでしょうか?

どちらにしても修正した方が良いのは確かなんですが、
このあたりの決着は着けておきたい気がします。

2 件のコメント:

  1. 過去の記事にすみません。SQLには再帰CTEがあるため、DMLの範囲でもbfは実装可能です。 http://bleis-tift.hatenablog.com/entry/20090610/1244615237

    返信削除
    返信
    1. 一年以上経過しての返信ですいません。
      ああ、SQL Serverではあるんですね…と言おうとしましたが、
      普通にSQL99で再帰クエリ(WITH RECURSIVE)があるじゃないですか!?
      やっぱりろくに調べもせずに言うものじゃないですね。

      削除