チューリング完全

みなさま ラムダ計算 をご存知でしょうか。 ラムダ計算はある種の関数型プログラミング言語の体系で、変数と関数, そして関数適用というミニマルな構成要素だけでチューリング完全な表現力を持っています。 この記事では、ラムダ計算の中でも特に単純な 型無しラムダ計算 に着想を得てラムダ計算のステップ評価器を作っている話について書きます。 既存のモデルへの不満 型無しラムダ計算の処理系は昔からいくつも実装されていて、有名なところで Unlambda や Lazy_K などがあります。 どちらも SKI コンビネーター理論 に基づいていて、 s, k, i という たった3つの組み込み関数でプログラムを記…

こんにちは、技術部の谷脇です。 去る2月10日に行われたYAPC::Hiroshima2024ですが、みなさまはいかがだったでしょうか。私は参加して大満足であり、運営の方々に大感謝させていただきます。 さて、カヤックではゴールドスポンサーと椅子スポンサーをしていたというのは開催直前に出した記事で述べさせていただきました。 techblog.kayac.com この記事では伏せられていた、椅子スポンサーのPerlbatrossですが、この記事ではPerlbatrossの内容紹介と問題解説をしようと思います。 Perlbatrossとは YAPC::Hiroshima2024の開催期間中にコードゴ…

わずか1.8KBでReactみたいなことができちゃうスゴイ奴！

はじめに Semiotics 誌への寄稿論文の編集である田中久美子『記号と再帰』（東京大学出版会）を読んだ。 応用記号論という伝統を墨守した真面目な論である。 石田英敬の情報記号論に失望した人々には受けると思う（計算機科学者ではなく仏文学者がなぜ情報記号論を建設できるのかという疑問は至極当然であろう。彼の著作を読めば、その情報学の専門性の低さには絶望する）。 西垣通から推されて書いたらしいが、なんかその実情が停滞していることを表しているというか、なんかなぁという。 情報学環の内輪ということにはなってしまうのかなと。 用いられる情報科学の知識は極めて基礎的であるものの、記号論のプログラム言語への…

この記事はいろいろなコンピューター Advent Calendar 2023の9日目の記事です。 adventar.org Brainf*ckとは Brainf*ck(この記事では一部伏字にして表記しています)は難解プログラミング言語のひとつです。 コンパイラがなるべく単純になるように設計されており、わずか8種の命令+ - > < [ ] . ,のみが存在する手続き型プログラミング言語です*1。 詳しい言語仕様等はEsolang wikiの記事 brainfuck - Esolang 等を参考にしてください。 仕様は単純ですが、チューリング完全なので、理論上はどんな計算でもすることができます。…

こんにちは！ HapInSアドベントカレンダー2023、8日目を担当するh_shimakawaです。 今回も引き続きラムダ計算を続けていきます。 はじめに 難易度 目標 用意するもの ひき算の作成準備 PAIR と LEFT、RIGHT の実装 SLIDE DEC の定義 ひき算 わり算の準備 LE 無名再帰関数 Z コンビネータ FIX コンビネータ MOD(割り算の余り)の定義 DIVの定義 さあ展開しよう！ 今回はここまで はじめに ラムダ計算第１回記事では、真偽値と数値、たし算とかけ算を定義しました。 今回は引き算と割り算の定義を行います。 ひき算とわり算の実装には、思ったよりたくさん…

これは言語実装のカレンダー | Advent Calendar 2023 - Qiitaの1日目の記事です。 このカレンダーを読んでいる皆さんなら、論文 「なぜ関数プログラミングは重要か」 に感銘を受けたりして、関数型言語を実装したいと思ったことがあるでしょう。 とはいえ、haskellやMLのような複雑な仕様を持つ言語では、 それに見合った複雑な実装が必要となって手に負えない、 と思った方も多いと思います。 しかし、LISPやforthのような単純な実装で済む処理系であれば、 一度は実装してみたことが、このカレンダーを読んでいる皆さんにはあるはずです。 私の自作言語revapp は、先の論文…

こんにちは。 今回は、プログラミング言語「Piet」を紹介します。 実は最近、こんなツイートをしました。 自己紹介。 pic.twitter.com/qc3IJRT4qD— taq (@taq2777) 2023年9月24日 これを見て"自己紹介"を感じていただけたならそれはそれで芸術の面白さを感じますが、芸術に疎い私にはこの画像に自己を乗せるというような高尚な表現はできないので、別の意味を持たせてあります。 それが今回紹介するプログラミング言語「Piet」に関わってきます。 目次 「Piet」とは 仕様 コーディング 自己紹介 本家に寄せたバージョン まとめ 「Piet」とは Piet は難…

振り返り日記、週一ぐらいにしよう。な。 出来もしないルールを掲げても形骸化しちゃうなんて、そんなん職場の安全ルールだけで十分や 仕事の話。 社会人生活始まって以来のゲキヤバデスマーチが続いており，スーパーコルサに引け劣らないスピードでメンタルが削れていく。 なにやってたかっていうと…8月の頭に実機が入ってから，ずっとそれのデバッグ。ずーーっと。ずっとずっと。 なれないラダー言語（そもそもアレは””言語””なのか？ チューリング完全なのか？？）で安川のサーボを恐る恐る動かし，LANを這わせてフィールドネットワークを構築し，キーエンスのライトカーテンのビットをシバく…たまにキーエンスの営業さんと雑…

応募課題はこちらに記載されています．また，内容は少しいじりました． https://www.ipa.go.jp/jinzai/security-camp/2023/next/ps6vr7000000c62g-att/next.txt 以下について，フリーフォーマットで自由に記述し回答してください． 選考のポイント 基本として、加点法で判断します。 自身の技術力ややってきたこと、発信してきたこと、何ができるかといったことなど、アピールしたい点を存分に記述してください。 多く書くことにより、「文章が長過ぎる・まとまりが無い・重複している・冗長」などとして減点するようなことはありません。 失敗した経…

私たちが日常的に触れる「数独」というパズルは、3x3のマスを9つ組み合わせた9x9の盤面に、1から9までの数字を重複無く配置することが求められるゲームである。しかしながら、ここでは「チューリング完全な数独」について考察していこう。これは数独のゲームルールを元に、チューリングマシンと同じ計算能力を持つとされる、深淵に触れるようなトピックだ。 「チューリング完全」という概念を理解するためには、まずはチューリングマシンの概念に触れる必要がある。チューリングマシンとは、コンピュータの理論的なモデルであり、どんなアルゴリズムも実行できるとされている。そのため「チューリング完全」なシステムとは、このチュー…

現代コンピュータの背景：チューリングマシンと計算不可能性 チューリングマシンの理論は、計算可能性という重要な概念を示しており、数学やコンピュータ科学において基礎的な役割を果たしています。チューリングマシンの理論に基づくと、計算問題は「計算可能」または「計算不能」の2つに分類されます。