Smn定理

s_mn定理 (英: s_mn theorem) もしくはパラメータ定理 (英: parameterization theorem) とは、再帰理論における定理であり、プログラミング言語（より一般化すれば、計算可能関数のゲーデル数）の基盤となっている^[1]^[2]。これを最初に証明したのはスティーブン・コール・クリーネである^[3]。s-m-n定理と表記されることもある。

この定理を実用的に解説すると、あるプログラミング言語と正の整数 m と n があるとき、m+n 個の自由変数を持つプログラムのソースコードを操作する特定のアルゴリズムがあることを示している。そのアルゴリズムは、与えられた m 個の値を最初の m 個の自由変数に束縛し、残りの変数を自由変数のままにしておく。

詳細

本定理の基本形は、2引数の関数に適用される。再帰関数のゲーデル数 $\varphi$ が与えられたとき、次のような性質の2引数の原始再帰関数 s が存在する。すなわち、あらゆる2引数の関数 f のゲーデル数 p について、同じ x と y の組合せでの $\varphi _{s(p,x)}(y)$ と $f(x,y)$ が定義され、その組合せにおいて等しい。言い換えれば、次のような外延的等価性が成り立つ。

\varphi _{s(p,x)}=\lambda y.\varphi _{p}(x,y)\,

これを一般化するため、元の数を原始再帰関数で引き出せるように、n 個の数を1つの数に符号化する方法を採用する。例えば、それらの数のビットをインターリーブするといった符号化が考えられる。すると任意の正の数 m と n について、m+1 個の引数をとる原始再帰関数 $s_{n}^{m}$ が存在し、次のように振舞う。すなわち、あらゆる m+n 引数の関数のゲーデル数 p について、

\varphi _{s_{n}^{m}(p,x_{1},\dots ,x_{m})}=\lambda y_{1},\dots ,y_{n}.\varphi _{p}(x_{1},\dots ,x_{m},y_{1},\dots ,y_{n})\,

となる。 $s_{1}^{1}$ は、関数 s そのものである。

例

以下のLISPのコードは、s₁₁ を実装したものである。

(defun s11 (f x)
  (list 'lambda '(y) (list f x 'y))

例えば、(s11 '(lambda (x y) (+ x y)) 3) を評価すると (lambda (y) ((lambda (x y) (+ x y)) 3 y)) になる。

脚注

^ Soare, R. (1987年). Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-15299-7
^ Rogers, H. (1987年) [1967年]. The Theory of Recursive Functions and Effective Computability. First MIT press paperback edition. ISBN 0-262-68052-1
^ Kleene, S. C. (1943年). “General recursive functions of natural numbers”. Mathematische Annalen 53: 727–742.

参考文献

Odifreddi, P. (1999年). Classical Recursion Theory. North-Holland. ISBN 0-444-87295-7

外部リンク

Weisstein, Eric W. "Kleene's s-m-n Theorem". mathworld.wolfram.com (英語).

Read other articles:

Laima Balaišytė

Laima Balaišytė (Amelin)Balaišytė-Amelina (1971)Informasi pribadiKewarganegaraan LituaniaLahir03 Januari 1948 (umur 76)VilniusPasanganAnatoly Amelin Rekam medali Putri Tenis Meja Mewakili Uni Soviet Kejuaraan Tenis Meja Dunia 1967 Stockholm Women's team 1969 Munich Women's team Laima Balaišytė (nama lain Laima Amelin; lahir 3 Januari 1948) adalah mantan pemain tenis meja putri asal Lithuania. Karier tenis meja Dia memenangkan medali perak di Kejuaraan Tenis Meja Dunia 19...

Comboios de Portugal

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada April 2016. Comboios de PortugalIndustriTransportasi relDidirikan1951KantorpusatLisbon, PortugalTokohkunciManuel Queiró,Vicente Pereira,Isabel VicenteProdukTransportasi rel, KargoPendapatan € -225.6 juta (2013)[1]Laba operasi € -75.35 juta (2013)[1&...

International Phonetic Alphabet chart

Phonetic symbol chart This article contains phonetic transcriptions in the International Phonetic Alphabet (IPA). For an introductory guide on IPA symbols, see Help:IPA. For the distinction between [ ], / / and ⟨ ⟩, see IPA § Brackets and transcription delimiters. The following is the chart of the International Phonetic Alphabet, a standardized system of phonetic symbols devised and maintained by the International Phonetic Association. It is not a co...

SMA Negeri 1 Ciparay

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapik...

U.S. Route 52 in Ohio

Section of U.S. Highway in Ohio This article is about the section of U.S. Route 52 in Ohio. For the entire route, see U.S. Route 52. U.S. Route 52US 52 highlighted in redRoute informationMaintained by ODOTLength180.968 mi[1] (291.240 km)Touristroutes Ohio River Scenic BywayMajor junctionsWest end US 52 / I-74 at the Indiana state line near HarrisonMajor intersections I-275 near Blue Jay US 27 in Cincinnati I-75 in Cincinnati US 127 in Cinci...

Mario Impemba

American sportscaster Mario ImpembaImpemba in Germany in 2013Born1962 or 1963 (age 60–61)Detroit, Michigan, U.S.Alma materMichigan State UniversityOccupationSportscasterSports commentary careerTeamsAnaheim Angels (1995–2001)Detroit Tigers (2002–2018)Boston Red Sox (2019)GenrePlay-by-playSportMajor League Baseball Mario Impemba (born 1962 or 1963)[1] is an American sportscaster, best known as the television play-by-play announcer for the Detroit Tige...

Gaetano Cicognani

Gaetano Cicognani BiografiKelahiran26 November 1881 Brisighella Kematian5 Februari 1962 (80 tahun)Roma Kardinal 12 Januari 1953 – Apostolic Nuncio to Spain 16 Mei 1938 – 12 Januari 1953 Apostolic Nuncio to Austria 14 Juni 1936 – 16 Mei 1938 Apostolic nuncio to Perú 20 Mei 1928 – Apostolic nuncio to Bolivia 11 Februari 1925 – Uskup agung Katolik 1r Februari 1925 – Titular archbishop 2 Januari 1925 – Keuskupan: Ancyra Data pribadiAgamaGereja Kat...

Sam Brown (activist)

American anti-war activist, politician, and government official (born 1943) The cover of Action Update (August 16, 1979) showing Sam Brown (right), the Director of the Action Corps which administered the Peace Corps, Volunteers in Service to America (VISTA) and other service programs. Richard Celeste (left) was appointed Peace Corps director after the resignation of Peace Corps Director Carolyn Payton. The cover of Action Update (September 30, 1979) depicting Sam Brown, who was appointed Dire...

Liste des comtes de Metz

En 870, le traité de Meerssen fait entrer le comté de Metz dans le domaine de Louis le Germanique[1]. Il y a eu à Metz deux sortes de comtes : les comtes royaux ainsi nommés parce qu’ils étaient investis par le roi des Francs, puis le roi de Germanie[2]. les comtes palatins nommés par les évêques de Metz pour gérer leurs affaires ; ils exercent en même temps que les comtes royaux. au XIe siècle, l’influence de l’empereur germanique, héritier des rois de German...

Dream Street (film)

Dream StreetSutradaraD. W. GriffithDitulis olehRoy SinclairBerdasarkanGina of Chinatown dan Song of the Lampoleh Thomas BurkePemeranCarol DempsterCharles Emmett MackRalph GravesTyrone Power, Sr.NaratorD. W. GriffithPenata musikLouis SilversIrving BerlinSinematograferHenrik SartovDistributorUnited ArtistsTanggal rilis 12 April 1921 (1921-04-12) Durasi135 menit[1]NegaraAmerika SerikatBahasaAntarjudul Inggris Dream Street adalah sebuah film drama romansa bisu Amerika Serikat t...

Breakaway (biscuit)

Brand of chocolate-covered digestive biscuit from Nestlé This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Breakaway biscuit – news · newspapers · books · scholar · JSTOR (August 2010) (Learn how and when to remove this message) BreakawayProduct typeDigestive biscuitOwnerNestléCountryUnited KingdomIntroduced1970; 54 years ago (197...

Klingon

Lambang Klingon Klingon (bahasa Klingon: tlhlngan) adalah ras humanoid dari planet Qo'noS (baca Kronos). Klingon adalah sebuah ras yang menganggap diri mereka sendiri sebagai ras pejuang. Klingon dikenal sebagai sebuah ras dengan kekaisaran militeristik yang disegani. Hal tersebut tidak lepas dari budaya mereka yang agresif. Klingon adalah satu-satunya ras alien dalam serial Star Trek yang memiliki bahasa yang digarap serius. Bahasa Klingon telah menjadi satu-satunya bahasa yang dibukukan dan...

Landstinget

Historic house of the Parliament of Denmark For other uses, see Landsting (disambiguation). You can help expand this article with text translated from the corresponding article in Danish. (June 2023) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-transla...

Theravada

Major branch of Buddhism Part of a series onTheravāda Buddhism Countries Bangladesh Cambodia China India Laos Myanmar Nepal Sri Lanka Thailand Vietnam Western world Texts Pāli Tipiṭaka Paracanonical texts Commentaries Sub-commentaries Vimuttimagga Visuddhimagga Abhidhammavatara Abhidhammattha-sangaha Yogāvacara's manual History Pre-sectarian Buddhism Early schools Sthaviras Buddhist councils Vibhajjavada Mahāvihāra Dipavamsa Mahavamsa Pali Text Society Schools Buddhist modernism Vipass...

Austria Dalam

Peta akhir abad ke-XVIII provinsi Habsburg Innerösterreich: Kadipaten Steiermark Kadipaten Kärnten Kadipaten Krain dengan wilayah Graft Duino dan Marka Istria Grafschaft Kepangeranan Gorizia dan Gradisca Kota Kekaisaran Trieste Austria Dalam (bahasa Jerman: Innerösterreich; bahasa Slovenia: Notranja Avstrija; bahasa Italia: Austria Interiore) adalah istilah yang digunakan dari akhir abad ke-XIV hingga awal abad ke-XVII untu...

Doppelkupplungsgetriebe

VW-Direktschaltgetriebe (DSG) Ein Doppelkupplungsgetriebe ist ein automatisiertes Schaltgetriebe, das mittels zweier Teilgetriebe einen vollautomatischen Gangwechsel ohne Zugkraftunterbrechung ermöglicht. Die Getriebesteuerung wählt die Gänge selbsttätig oder nach Fahrerwunsch (Schaltwippen/Wählhebel) im Rahmen der zugelassenen Drehzahlbereiche. Im Gegensatz zu Automatikgetrieben mit hydraulischem Drehmomentwandler erfolgt die Übertragung des Moments über eine von zwei Kupplungen, die ...

Narnarayan Dev Yuvak Mandal

Hindu organisation This article may rely excessively on sources too closely associated with the subject, potentially preventing the article from being verifiable and neutral. Please help improve it by replacing them with more appropriate citations to reliable, independent, third-party sources. (May 2013) (Learn how and when to remove this message) NarNarayan Dev Yuvak MandalNNDYM LogoAbbreviationNNDYMFormationYear 1994TypeNGOPurposeHumanitarian and religiousHeadquartersShri Swaminarayan Mandi...

Atlanta University Center

Educational consortium of HBCUs in Atlanta, Georgia, United States Atlanta University Center Consortium, Inc.AUC ConsortiumClockwise from top left: Clark Atlanta University, Morehouse College, Spelman College, Morehouse School of MedicineFormationApril 1, 1929; 95 years ago (1929-04-01)TypeNon-profit higher education consortiumLocationAtlanta, Georgia, United StatesWebsitewww.aucenter.edu The Atlanta University Center Consortium (AUC Consortium) is a collaboration between fo...

鬼平犯科帳 (十代目松本幸四郎)

鬼平犯科帳 > 鬼平犯科帳 (テレビドラマ) > 鬼平犯科帳 (十代目松本幸四郎) 十代目松本幸四郎主演・『鬼平犯科帳』（おにへいはんかちょう）は、日本映画放送を中心とする時代劇パートナーズにより2024年1月より展開されているテレビ時代劇である。連動して公開された日本映画『鬼平犯科帳血闘』（おにへいはんかちょうけっとう）についても解説する�...

Pre-sectarian Buddhism

Part of a series onEarly Buddhism Scriptures Early Buddhist Texts (EBT) Tripiṭaka Nikayas Āgamas Gandhāran EBTs Prātimokṣa Abhidharma Jatakas Avadanas Mahāvastu Śālistamba Sūtra Tibetan EBTs in the Kangyur Early sangha Gautama Buddha Sāriputta Mahāmoggallāna Mahāpajāpatī Gotamī Mahakasyapa Ānanda Upāli Mahākātyāyana Devadatta Anāthapiṇḍika Pre-sectarian Buddhism Kingdom of Magadha Ashoka Moggaliputtatissa Buddhist councils Early Buddhist schools Pre-sectarian Buddh...

PROFILPELAJAR.COM