翻訳と辞書 Words near each other ・ Elena (opera) ・ Elena (play) ・ Elena (Street Fighter) ・ Elena (telenovela) ・ Elena (village) ・ Elena Abramovich ・ Elemental Records ・ Elemental Technologies ・ Elementalors ・ Elementals (Comico Comics) ・ Elementals (comics) ・ Elementals (DC Comics) ・ Elementals (Marvel Comics) ・ Elementalz ・ Elementar ・ ELEMENTARY ・ Elementary ・ Elementary (Cindy Morgan album) ・ Elementary (The End album) ・ Elementary (TV series) ・ Elementary abelian group ・ Elementary algebra ・ Elementary amenable group ・ Elementary and Secondary Education Act ・ Elementary and secondary public schools in Ottawa ・ Elementary arithmetic ・ Elementary calculus ・ Elementary cellular automaton ・ Elementary charge ・ Elementary class Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ELEMENTARY ： ウィキペディア英語版 ELEMENTARY In computational complexity theory, the complexity class ELEMENTARY of elementary recursive functions is the union of the classes : $\backslash begin$ \mathrm & = \mathrm\cup\mathrm\cup\mathrm\cup\cdots \\ & = \mathrm(2^n)\cup\mathrm(2^)\cup \mathrm(2^ The name was coined by László Kalmár, in the context of recursive functions and undecidability; most problems in it are far from elementary. Some natural recursive problems lie outside ELEMENTARY, and are thus NONELEMENTARY. Most notably, there are primitive recursive problems that are not in ELEMENTARY. We know :LOWER-ELEMENTARY $\backslash subsetneq$ EXPTIME $\backslash subsetneq$ ELEMENTARY $\backslash subsetneq$ PR $\backslash subsetneq$ R Whereas ELEMENTARY contains bounded applications of exponentiation (for example, $O(2^)$), PR allows more general hyper operators (for example, tetration) which are not contained in ELEMENTARY. ==Definition== The definitions of elementary recursive functions are the same as for primitive recursive functions, except that primitive recursion is replaced by bounded summation and bounded product. All functions work over the natural numbers. The basic functions, all of them elementary recursive, are: # Zero function. Returns zero: ''f''(x) = 0. # Successor function: ''f''(''x'') = ''x'' + 1. Often this is denoted by ''S'', as in ''S''(''x''). Via repeated application of a successor function, one can achieve addition. # Projection functions: these are used for ignoring arguments. For example, ''f''(''a'', ''b'') = ''a'' is a projection function. # Subtraction function: ''f''(''x'', ''y'') = ''x'' − ''y'' if ''y'' < ''x'', or 0 if ''y'' ≥ ''x''. This function is used to define conditionals and iteration. From these basic functions, we can build other elementary recursive functions. # Composition: applying values from some elementary recursive function as an argument to another elementary recursive function. In ''f''(''x''1, ..., ''x''n) = ''h''(''g''1(''x''1, ..., ''x''n), ..., ''g''m(''x''1, ..., ''x''n)) is elementary recursive if ''h'' is elementary recursive and each ''g''i is elementary recursive. # Bounded summation: $f(m,\; x\_1,\; \backslash ldots,\; x\_n)\; =\; \backslash sum\backslash limits\_^mg(i,\; x\_1,\; \backslash ldots,\; x\_n)$ is elementary recursive if ''g'' is elementary recursive. # Bounded product: $f(m,\; x\_1,\; \backslash ldots,\; x\_n)\; =\; \backslash prod\backslash limits\_^mg(i,\; x\_1,\; \backslash ldots,\; x\_n)$ is elementary recursive if ''g'' is elementary recursive. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ELEMENTARY」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.