SKI combinator calculus (original) (raw)

About DBpedia

SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない（難解プログラミング言語には時折採用される）。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある。 ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI（これらをコンビネータと呼ぶ）および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。

Property Value
dbo:abstract The SKI combinator calculus is a combinatory logic system and a computational system. It can be thought of as a computer programming language, though it is not convenient for writing software. Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language. It can be likened to a reduced version of the untyped lambda calculus. It was introduced by Moses Schönfinkel and Haskell Curry. All operations in lambda calculus can be encoded via abstraction elimination into the SKI calculus as binary trees whose leaves are one of the three symbols S, K, and I (called combinators). (en) SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない（難解プログラミング言語には時折採用される）。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある。 ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI（これらをコンビネータと呼ぶ）および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。 (ja) Os combinadores SKI são um modelo computacional que pode ser percebido como uma versão reduzida do cálculo lambda não tipado. Ele pode ser pensado como uma linguagem de programação de computador, apesar de não ser útil para escrever software. Em vez disso, é importante na teoria matemática de algoritmos porque é uma linguagem Turing completa e extremamente simples. Todas as operações em cálculo lambda são expressas em SKI como árvores binárias, cujas folhas são um dos três símbolos S, K e I (chamados de combinadores). Na verdade, o símbolo I está incluído apenas por conveniência, pois os outros dois são suficiente para todos os efeitos do sistema SKI. Embora a representação mais formal dos objetos neste sistema exija árvores binárias, são representados geralmente, por typesetability, como expressões entre parênteses, quer com todas as subárvores entre parênteses, ou apenas os do lado direito das subárvores entre parênteses. Assim, a árvore cuja esquerda subárvore é a árvore KS e cuja subárvore direita é a árvore SK, normalmente é digitada como ((KS) (SK)), ou mais simplesmente como KS (SK), em vez de ser totalmente desenhado como uma árvore (como a formalidade e a legibilidade exigiria). (pt) SKI组合子演算是一个计算系统，它是对无类型版本的Lambda演算的简约。这个系统声称在Lambda演算中所有运算都可以用三个组合子S、K和I来表达。 在这个系统中的所有函数可以只使用S、K、I的字母表和圆括号（分组符号）来表达。通常假定组合子是左结合的，从而在不影响执行次序的情况下精简表达式中的圆括号。 (zh)
dbo:wikiPageExternalLink http://dkeenan.com/Lambda/index.htm http://www.angelfire.com/tx4/cus/combinator/birds.html https://web.archive.org/web/20081029051502/http:/cstein.kings.cam.ac.uk/~chris/combinators.html http://people.cs.uchicago.edu/~odonnell/Teacher/Lectures/Formal_Organization_of_Knowledge/Examples/combinator_calculus/ http://www.lfcs.inf.ed.ac.uk/reports/89/ECS-LFCS-89-85/ https://web.archive.org/web/20131014210033/http:/www.urbit.org/2013/08/22/Chapter-2-nock.html
dbo:wikiPageID 1232841 (xsd:integer)
dbo:wikiPageLength 15465 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1114228209 (xsd:integer)
dbo:wikiPageWikiLink dbr:Binary_tree dbr:Algorithm dbc:Lambda_calculus dbc:Combinatory_logic dbr:Unlambda dbr:Intuitionistic_logic dbr:Peirce's_law dbr:Combinatory_logic dbr:Moses_Schönfinkel dbr:Functional_programming dbr:Turing_complete dbr:To_Mock_a_Mockingbird dbr:Law_of_excluded_middle dbr:Graph_reduction dbr:Fixed_point_combinator dbr:Recursion dbr:Haskell_Curry dbr:Iota_and_Jot dbr:Lambda_calculus dbr:Syntactic_sugar dbr:Modus_ponens dbr:B,_C,_K,_W_system dbr:Classical_logic dbr:Implicational_propositional_calculus dbr:Sentential_logic dbr:Model_of_computation dbr:Boolean_logic dbr:Curry–Howard_isomorphism
dbp:wikiPageUsesTemplate dbt:Cite_book dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Nobold
dct:subject dbc:Lambda_calculus dbc:Combinatory_logic
gold:hypernym dbr:System
rdfs:comment SKIコンビネータ計算は型無しラムダ計算を単純化した、ひとつの計算モデルである。このモデルは、ある種のプログラミング言語と考えることができるが、人間によるソースコードの記述には適さない（難解プログラミング言語には時折採用される）。その代わり、このモデルは非常に単純なチューリング完全な言語であるため、アルゴリズムの数学理論においては重要である。また関数型言語を実行する抽象機械のモデルとして使っている例もある。 ラムダ計算におけるあらゆる演算は、SKIにおいて3つの定数記号S, KおよびI（これらをコンビネータと呼ぶ）および変数記号によって表現できる。2引数の関数適用演算のみを持つ形式言語の構文木と考えれば、定数記号と変数記号を葉とする二分木と捉えることもできる。 実際には、 I はモデルを簡単にするために導入されたものであり、SKIシステムを展開するにはSとKの2つで十分である。 (ja) SKI组合子演算是一个计算系统，它是对无类型版本的Lambda演算的简约。这个系统声称在Lambda演算中所有运算都可以用三个组合子S、K和I来表达。 在这个系统中的所有函数可以只使用S、K、I的字母表和圆括号（分组符号）来表达。通常假定组合子是左结合的，从而在不影响执行次序的情况下精简表达式中的圆括号。 (zh) The SKI combinator calculus is a combinatory logic system and a computational system. It can be thought of as a computer programming language, though it is not convenient for writing software. Instead, it is important in the mathematical theory of algorithms because it is an extremely simple Turing complete language. It can be likened to a reduced version of the untyped lambda calculus. It was introduced by Moses Schönfinkel and Haskell Curry. (en) Os combinadores SKI são um modelo computacional que pode ser percebido como uma versão reduzida do cálculo lambda não tipado. Ele pode ser pensado como uma linguagem de programação de computador, apesar de não ser útil para escrever software. Em vez disso, é importante na teoria matemática de algoritmos porque é uma linguagem Turing completa e extremamente simples. (pt)
rdfs:label SKIコンビネータ計算 (ja) SKI combinator calculus (en) Combinadores SKI (pt) SKI组合子演算 (zh)
owl:sameAs freebase:SKI combinator calculus wikidata:SKI combinator calculus dbpedia-hr:SKI combinator calculus dbpedia-ja:SKI combinator calculus dbpedia-pt:SKI combinator calculus dbpedia-zh:SKI combinator calculus https://global.dbpedia.org/id/51UNx
prov:wasDerivedFrom wikipedia-en:SKI_combinator_calculus?oldid=1114228209&ns=0
foaf:isPrimaryTopicOf wikipedia-en:SKI_combinator_calculus
is dbo:wikiPageDisambiguates of dbr:Ski_(disambiguation)
is dbo:wikiPageRedirects of dbr:SKI-calculus dbr:SKI_calculus dbr:SKI_combinator dbr:SK_calculus dbr:SK_combinator_calculus dbr:Ski_combinators
is dbo:wikiPageWikiLink of dbr:List_of_functional_programming_topics dbr:Unlambda dbr:Combinatory_logic dbr:Monad_(functional_programming) dbr:To_Mock_a_Mockingbird dbr:Iota_and_Jot dbr:Lambda_calculus dbr:Binary_combinatory_logic dbr:Coders_at_Work dbr:B,_C,_K,_W_system dbr:Categorical_abstract_machine dbr:Ski_(disambiguation) dbr:Fixed-point_combinator dbr:SKI-calculus dbr:SKI_calculus dbr:SKI_combinator dbr:SK_calculus dbr:SK_combinator_calculus dbr:Ski_combinators
is rdfs:seeAlso of dbr:Lambda_calculus
is foaf:primaryTopic of wikipedia-en:SKI_combinator_calculus