ラムダ計算とチューリングマシンの違い 2009-04-13 - きしだのはてな
ぼくもYコンビネータがわかるようになるまではそうだったのだけど、Yコンビネータを使うとどのような処理ができるのかがよくわからなくて悩んでいる人が多いように思う。他の人のブログを見ても、名前をつけずに再帰ができるのがすばらしいとか書いてあったりするのだけど、それによってどういう処理ができるのかわからずにいた。 結論をいえばYコンビネータには、なにかの処理を便利にする能力はない。関数であらゆる計算ができるということが示せれば、あとは用なしだ。理論の礎としてうまってしまえばいい。 結局、Yコンビネータによってどのような処理ができるかというのは、ラムダ計算の要素のメリットをチューリングマシンの中に見出そうとしてるといえる。 ラムダ計算とチューリングマシンは、どちらも計算モデルという点では一致しているけど、全く違う。 無限であるか有限かの違いといってもいい。 チューリングマシンでは、データの量と処理
さあ、Yコンビネータ(不動点演算子)を使おう！ - よくわかりません
前回、おとうさんにもわかるYコンビネータ！(絵解き解説編) - よくわかりませんというエントリで、Yコンビネータ(不動点演算子)と再帰の絵解き解説をしました。 Yコンビネータ自身は、結局のところ再帰を産み出してくれるだけです。関数(正確にはλという単純な文字列変換ルール)だけで出来て、プログラミングに関するいろんな原理の研究を可能にするのが凄い訳です。その辺のさわりを、きしださんが解説されています。しかし、単なる再帰なら、実際のプログラミングではYコンビネータなんて使わなくても出来ます。 じゃあ、Yコンビネータとか不動点とかは、偉い学者さんとかが研究に使えばいいもので、普通のプログラマには何の意味もないモノなのでしょうか？ というわけで、今回はポジティブに、Yコンビネータや不動点で出てくる考え方を、理論だけじゃなく、実際のプログラミングに応用する例を見てみましょう。 今回、プログラムの例を
不動点コンビネータ - Wikipedia
「Yコンビネータ」は不動点演算子について説明しているこの項目へ転送されています。カリフォルニア州の企業については「Yコンビネータ (企業)」をご覧ください。 不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数 の不動点とは、 を満たすような のことをいう。 すなわち高階関数 が不動点コンビネータであるとは、 任意の関数 に対し、 とすると, が成立する 事を指す。 あるいは全く同じことだが、不動点コンビネータの定義は、任意の関数 に対し、 が成立する事であるとも
Lisper のためのチューリングマシンの停止性問題 - あどけない話
停止性問題を読んでも、意味が分からなかった Lisper のために、Lisp のコードで停止性を解説してみる。使用する Lisp としては、Scheme、Common Lisp、Emacs Lisp を検討したが、Emacs Lisp が一番よいと分かったので、Emacs Lisp を使う。 名前を使った概略 halt-p というプログラムは、入力としてプログラム p とデータ d を取る。Lisp なので、p も d も S 式である。halt-p は、p と d を検査し、p に d を与えたときに、停止するか否かを有限時間で判断する。停止するなら t、停止しないなら nil を返す。 machine というプログラムは、入力 x に対して以下のような動作をする。 (halt-p x x) が t なら、(machine x) を呼び出すことで同じ作業を繰り返す つまり、x に x 自
翻訳:プログラミング言語Lazy_K
このページは、Lazy K公式サイトの翻訳です。 http://homepages.cwi.nl/~tromp/cl/lazy-k.html 基本的に超訳です。 訳の正しさは全く保証されません。 訳のおかしい部分は多数あります。 翻訳元サイトの許可を取ったりはしていません。 無認可です。 訳者による前書き / 訳語についてLazy K要約サンプルコード何故Lazy Kが必要とされるのかLazy KのI/OLazy Kの構文と動作Lazy Kの失脚Lazy KインタープリタLazy Kコンパイラサンプルコードバグと欠点訳者による感想 / 要約 / その他コメントその他 訳者による前書き / 訳語について この文書はとりあえず、Lisp(できればScheme)を理解してる人向け。 動作の説明例がlambdaで書いてあったり、Lazy KコンパイラでScheme処理系が必要になったりする為。 C
Webアプリケーション設計と継続 | oldwaveの日記 | スラド
Webアプリケーションの設計をするとき、Schemeでいう継続(continuation)の概念を理解しておくと非常に役に立つ。 継続の概念は、なかなか理解が難しい。概念として理解できても、それが何に役立つのかわからないという人も多いだろう。実際、僕も継続の有効活用についてわかるようになるまで、何年もかかったし、今でも十分に馴染んでいると自負できるまでには至っていない。 しかし、最近になって気付いたのだが、Webアプリケーションというものは、ちょっと見方を変えてみると、GOTO文とグローバル変数の塊なのだ。そして継続はこういった問題を制御するための武器になる。 セッションに値を格納するとき、それが不変の値であれば良いが、状態を持つ場合、それはまったくグローバル変数そのものである。しかもWebアプリケーションの場合、複数のURIにまたがる処理はブラウザの「戻る」ボタンやブックマークによって、
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
404 Blog Not Found:Stiffと偉大なプログラマー達-プログラマーと数学・物理
2006年09月14日17:45 カテゴリBlogosphere Stiffと偉大なプログラマー達-プログラマーと数学・物理 引き続きSztywny Blog - Stiff asks, great programmers answerの翻訳。 今回の質問はこちら。 数学と物理は、プログラマーにとって重要?だとしたらなぜ? プログラマー達の解答は以下のとおり。 Dan the Translator Steve Yegge: 「離散数学」とか"concrete math"(訳注:「具象数学」?)と言われる分野は、プログラマーにとって非常に重要。確率、組み合わせ、グラフ理論、帰納的証明、その他の重要な道具がここに含まれている。 全てのプログラマーは、その能力の許す限り離散数学を学ぶべきだ。それがたとえわずかでも、ないよりはずっとずっとマシである。 その他の伝統的な数学に関しては、うーん、それほ
自動改札機の運賃計算プログラムはいかにデバッグされているのか？ 10の40乗という運賃パターンのテスト方法を開発者が解説（前編）
自動改札機の運賃計算プログラムはいかにデバッグされているのか？ 10の40乗という運賃パターンのテスト方法を開発者が解説（前編） ふだん何気なく使っている鉄道。改札を降りるときにICカードを自動改札にかざすと、「ピッ」という音と共に一瞬のうちに運賃を計算してくれます。けれど、複数の路線を乗り継いだり、途中で定期券区間が挟まっていたりと、想像しただけでもそこには膨大な組み合わせがあります。それでも運賃計算プログラムはわずか一瞬で正しい運賃計算が求められ、バグがあったら社会的な一大事にもつながりかねません。 爆発的な計算結果の組み合わせがあるはずの運賃計算プログラムは、どうやってデバッグされ、品質を維持しているのでしょうか？ 9月12日から14日のあいだ、東洋大学 白山キャンパスで開催された日本科学技術連盟主催の「ソフトウェア品質シンポジウム 2012」。オムロンソーシアルソリューションズ 幡
Implementing Regular Expressions
Implementing Regular Expressions Russ Cox rsc@swtch.com This page collects resources about implementing regular expression search efficiently. Articles and Notes “Regular Expression Matching Can Be Simple And Fast” An introduction to using finite automata to implement regular expression matching, and why the standard backtracking implementation is a bad idea. Supporting programs: NFA | DFA | bound
おねえさんのコンピュータ
同じ所を２度通らない道順の数 Total number of routes that do not pass by the same place twice
動的型言語のモラトリアム
Hideyuki Tanaka @tanakh 動的型のプログラミング言語がなぜ日本では軽量とみなされるようになったのか。これが一つの謎である。動的型はすなわちバグの発生を遅延しているに過ぎないのであるが、それを軽量というのであれば世の中のプログラムというものは正確さを必ずしも要求されないということだろうか。 2011-07-18 18:09:21 極端流形式仕様 初代𝕍𝕚𝕖𝕟𝕟𝕒𝕋𝕒𝕝𝕜𝕖𝕣 @tomooda 正確さだけが絶対なら有限精度の数値型を使うべきではないですね。 RT @tanakh それを軽量というのであれば世の中のプログラムというものは正確さを必ずしも要求されないということだろうか。 2011-07-18 18:18:43
Lisp:S式の理由
S式は人に優しいか Shiro: Lispの不人気の理由として筆頭に上げられるのが、括弧だらけの 独特の見た目。とっつきにくい、一般的な表記法と違っていてわかりにくい、 等々、様々なことが言われてきました。しかし、 S式を捨てたLispも開発されましたが 流行ったとはいい難く、Lispな人々はいまだに括弧に固執しているかのようです。 S式のメリットをLisperに尋ねれば、エディタがどうの、マクロがどうの、といった 回答が真っ先に返って来ると思うんですが、そういう理屈をいくら理解しても S式がダメな人がS式を好きになったりはしません。どうも、もっと根本的な 感覚に大きな隔たりがあるような気がします。非Lisperから理解しがたい、 Lisperの持つ感覚とはどんなものなんでしょうか。Lisp脳から見た世界は どんなものなのでしょうか。 構文木を人間が書く? S式は言ってみれば言語の構文木そ
RubyにおけるシーケンスはObject#repeatに任せなさい！
Rubyにおいてシーケンス、つまり意味的に連続する要素の並びを簡単に生成するObject#repeatというものを考えましたよ！以前に考えたEnumerable#repeatを単にすべてのオブジェクトに拡張したものですけど。 class Object def repeat(init=true, &blk) x = self Enumerator.new do |y| y << x if init loop { y << (x = yield x) } end end end repeatは、そのレシーバオブジェクトを初期値として、渡されたブロックを繰り返し適用します。適用の結果はEnumeratorオブジェクトでラップされているので、遅延評価されます。 以下に、問題に答える形で使い方を見せますね。比較のためrepeatを使わない方法も適宜示します。 1. 初項1、公差2の等差数列の最初の2
Asynchronous programming and continuation-passing style in JavaScript
Asynchronous programming and continuation-passing style in JavaScript In this blog post, we give a name to JavaScript’s callback-based asynchronous programming style: continuation-passing style (CPS). We explain how CPS works and give tips for using it. Asynchronous programming and callbacks If you have ever done asynchronous programming in JavaScript, you probably noticed that everything works di
rocco.rb
Rocco is a Ruby port of Docco, the quick-and-dirty, hundred-line-long, literate-programming-style documentation generator. Rocco reads Ruby source files and produces annotated source documentation in HTML format. Comments are formatted with Markdown and presented alongside syntax highlighted code so as to give an annotation effect. This page is the result of running Rocco against its own source fi
Freecode
Browse free open source Software Development software and projects below. Use the toggles on the left to filter open source Software Development software by OS, license, language, programming language, and project status. Connect your teams with an integrated digital workplace Wherever your teams work, keep them connected with a digital workplace that unifies all your productivity tools in one cen
Information Science and Statistics Series Editors: M. Jordan J. Kleinberg B. Scho¨lkopf Information Science and Statistics Akaike and Kitagawa: The Practice of Time Series Analysis. Bishop: Pattern Recognition and Machine Learning. Cowell, Dawid, Laurit
Information Science and Statistics Series Editors: M. Jordan J. Kleinberg B. Scho¨lkopf Information Science and Statistics Akaike and Kitagawa: The Practice of Time Series Analysis. Bishop: Pattern Recognition and Machine Learning. Cowell, Dawid, Lauritzen, and Spiegelhalter: Probabilistic Networks and Expert Systems. Doucet, de Freitas, and Gordon: Sequential Monte Carlo Methods in Practice. Fin
Beyond grep: ack 2.12, a source code search tool for programmers
ack is a grep-like source code search tool. The latest version of ack is v3.9.0, released 2025-05-26. Changelog for v3.9.0 Designed for programmers with large heterogeneous trees of source code, ack is written in portable Perl 5 and takes advantage of the power of Perl's regular expressions. What's new in ack? New boolean options --and, --or and --not The new repeatable --and, --or and --not optio
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
GitHub - vim-syntastic/syntastic: Syntax checking hacks for vim
