問題タブ [turing-complete]

この初心者の質問で申し訳ありませんが、友人にそれが可能かどうかを伝えるために、簡単な回答が必要です.

今朝、純粋な HTML5 + CSS3 (javascript なし) でルール 110 の次の実装に出くわしました。オートマトンを実行するには、タブとスペースを順番に押します。

http://elilies.com/rule110-full.html

ソースコードを見ましたが、どのように状態を追跡しているのか本当にわかりません。タブが押されると、:focus セレクターが機能するようになりますが、スペースが押されるとどうなるかはわかりません。

「辞書」とは、一意のキーを持つキーと値のペアの配列を意味します。そうでない場合、なぜですか？十分な長さであれば、キーを入力として、値を出力として使用でき、必要なだけ多くの問題の解決策を得ることができます。可能なすべての入力を保持するのに十分な長さである限り、何でも「計算」できます。入力に一定量のビットがあることが確立されている限り、これは無限である必要はありません。したがって、入力が X ビットであることに同意した場合、必要なのは 2^X 項目の辞書だけであり、X ビットを入力として受け取る可能性のあるすべてのチューリング マシンが得られます。

右？そうではないと思いますが、なぜですか？

スターバックスのミニ言語メニュー システムをある種の文法またはステート マシンとして解釈するとしたら、その文法はチューリング完全でしょうか? スターバックスの注文ミニ言語の説明は、ここにあります。

C++ テンプレート メタプログラミングがチューリング完全であることは知っています。同じことがプリプロセッサのメタプログラミングにも当てはまりますか?

つまり、精度の点でkinectに近いWebカメラ認識を記述します。

Ruby や Perl のプログラマーが、完全に正規表現のみを使用して複雑なコードの課題を解決しているのを見てきました。Perl 正規表現の先読み機能と後読み機能により、他のほとんどの言語の正規表現実装よりも強力になります。私は彼らが実際にどれほど強力なのか疑問に思っていました。

Perl 正規表現がチューリング完全であることを証明または反証する簡単な方法はありますか?

システム FI では、教会数を使用して真の全加算関数を定義できます。

Haskell では、下の値のためにその関数を定義できません。たとえば、haskell では、x + y = x の場合、y がゼロであるとは言えません。x が底の場合、任意の y について x + y = x です。したがって、足し算は真の足し算ではなく、その近似値です。

C仕様では、すべてに有限サイズが必要であるため、CIではその関数を定義できません。そのため、C では可能な近似は Haskell よりもさらに悪いものになります。

したがって、次のようになります。

System F では、加算を定義することはできますが、完全な実装を行うことはできません (無限のハードウェアがないため)。

Haskell では、追加を定義することはできず (底のため)、完全な実装を持つことはできません。

C では、合計加算関数を定義することはできません (すべてのセマンティックが制限されているため) が、準拠した実装は可能です。

したがって、3 つの正式なシステム (Haskell、システム F、および C) はすべて、設計上のトレードオフが異なるようです。

では、どちらか一方を選択すると、どのような結果が生じるでしょうか。

昨日、私は と呼ばれるプログラミング言語に関するこの記事をインターネットで見つけましたBrainFuck。 http://www.muppetlabs.com/~breadbox/bf/

だから私はこれが不思議です

では、それは本当に今日のチューリング完全プログラミング言語の最小のコンパイラなのでしょうか? とにかく、より小さなコンパイラが存在しないことが証明されていますか?

この分野での成果はありますか。とても興味があります.チューリング完全なプログラミング言語のコンパイラのサイズの最小値はありますか?その値は何ですか?

「チューリング完全性」の完全な定義には、無限のメモリが必要です。

有限 (100 ワードまたは 16 ビットまたは 32 ビットなど) のアドレス空間によって制限されることを除いて、完全に使用できるように見えるプログラミング言語および実装について、Turing Complete よりも適切な用語はありますか?