McCarthy 91 function (original) (raw)
La función 91 de McCarthy es una función recursiva, definida por el informático John McCarthy. La función está definida de la siguiente manera: Los resultados de evaluar la función están dados por M(n) = 91 para todo argumento entero n ≤ 100, y M(n) = n − 10 para n ≥ 101. * Datos: Q3075198
| Property | Value |
|---|---|
| dbo:abstract | La función 91 de McCarthy es una función recursiva, definida por el informático John McCarthy. La función está definida de la siguiente manera: Los resultados de evaluar la función están dados por M(n) = 91 para todo argumento entero n ≤ 100, y M(n) = n − 10 para n ≥ 101. * Datos: Q3075198 (es) The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science. The McCarthy 91 function is defined as The results of evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 100, and M(n) = n − 10 for n > 100. Indeed, the result of M(101) is also 91 (101 - 10 = 91). All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92, M(103) = 93. (en) La fonction 91 de McCarthy est une fonction récursive définie par McCarthy dans son étude de propriétés de programmes récursifs, et notamment de leur vérification formelle. Avec la fonction de Takeuchi, elle est un exemple amplement repris dans les manuels de programmation. (fr) マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 n ≤ 101 に対して 91 を返し、n > 101 に対しては を返す。計算機科学者ジョン・マッカーシーが考案した。 マッカーシーの91関数の定義は次の通り。 例 A: M(99) = M(M(110)) 99 ≤ 100 であるため = M(100) 110 > 100 であるため = M(M(111)) 100 ≤ 100 であるため = M(101) 111 > 100 であるため = 91 101 > 100 であるため 例 B: M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... このパターンが続く = M(99) （以下、例 A と同じ） = 91 ジョン・マッカーシーはこれを、自身が開発したLISP言語で次のように書いた。 (defun mc91 (n) (cond ((<= n 100) (mc91 (mc91 (+ n 11)))) (t (- n 10)))) この関数が期待通りに動作することの証明は次のようになる。 90 ≤ n < 101 のとき、 M(n) = M(M(n + 11)) = M(n + 11 - 10) なぜなら n >= 90 であるから n + 11 >= 101 となるため = M(n + 1) 従って 90 ≤ n < 101 のとき M(n) = 91 である。 以上を基本として、11個の数のブロック毎に証明していく。a ≤ n < a + 11 について M(n) = 91 であるとする。そのとき a - 11 ≤ n < a となるような任意の n について、 M(n) = M(M(n + 11)) = M(91) 仮定から、a ≤ n + 11 < a + 11 であるため = 91 基本ケースから 以上のように n をブロック単位で考えれば M(n) = 91 であることが求められる。ブロック間に抜けているところはないので、n < 101 の場合常に M(n) = 91 となる。また、n = 101 の場合を特殊例として追加することもできる。 (ja) In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che restituisce 91 per tutti gli argomenti n ≤ 101 e restituisce per . Limitatamente all'insieme degli interi minori di 102 essa, quindi, è un'endofunzione avente un unico punto fisso. Tale funzione fu ideata dall'informatico John McCarthy. La Funzione 91 di McCarthy è definita come segue: Esempi: M(99) = M(M(110)) dato che 99 ≤ 100 = M(100) dato che 110 > 100 = M(M(111)) dato che 100 ≤ 100 = M(101) dato che 111 > 100 = 91 dato che 101 > 100M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... continua = M(99) (come sopra) = 91 John McCarthy potrebbe aver scritto in questo modo la funzione, nel linguaggio di programmazione Lisp che lui stesso inventò: : (defun mc91 (n) (cond ((<= n 100) (mc91 (mc91 (+ n 11)))) (t (- n 10)))) Segue la dimostrazione del comportamento descritto della funzione:Per 90 ≤ n < 101, M(n) = M(M(n + 11)) = M(n + 11 - 10), poiché n >= 90 quindi n + 11 >= 101 = M(n + 1) Di conseguenza M(n) = 91 per 90 ≤ n < 101. Si può usare questo risultato come caso base per induzione su 11 numeri, in questo modo: Si assuma che M(n) = 91 per a ≤ n < a + 11. Allora, per ogni n tale che a - 11 ≤ n < a, M(n) = M(M(n + 11)) = M(91), per ipotesi, dato che a ≤ n + 11 < a + 11 = 91, per il caso base. Ora per induzione M(n) = 91 per ogni n in questo blocco. I blocchi così considerati sono adiacenti, senza spazi tra di loro, quindi M(n) = 91 per n < 101. Possiamo anche aggiungere n = 101 come caso speciale. (it) |
| dbo:wikiPageID | 222665 (xsd:integer) |
| dbo:wikiPageLength | 8316 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122572514 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Continuation dbr:Lisp_(programming_language) dbr:Strong_induction dbr:Computer_science dbr:Computer_scientist dbr:Zohar_Manna dbr:Mutual_recursion dbr:C_(programming_language) dbr:ACL2 dbr:Amir_Pnueli dbc:Recurrence_relations dbr:Formal_verification dbr:Formal_methods dbr:Haskell_(programming_language) dbc:Formal_methods dbr:John_McCarthy_(computer_scientist) dbr:Tail_recursion dbr:Mitchell_Wand dbr:Donald_Knuth dbr:Recursion_(computer_science) dbr:Extensionality dbr:Single_recursion dbr:Termination_proof dbr:OCaml_(programming_language) dbr:John_Cowles_(mathematician) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:No_footnotes dbt:Reflist dbt:John_McCarthy |
| dct:subject | dbc:Recurrence_relations dbc:Formal_methods |
| rdf:type | yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 yago:WikicatFormalMethods |
| rdfs:comment | La función 91 de McCarthy es una función recursiva, definida por el informático John McCarthy. La función está definida de la siguiente manera: Los resultados de evaluar la función están dados por M(n) = 91 para todo argumento entero n ≤ 100, y M(n) = n − 10 para n ≥ 101. * Datos: Q3075198 (es) The McCarthy 91 function is a recursive function, defined by the computer scientist John McCarthy as a test case for formal verification within computer science. The McCarthy 91 function is defined as The results of evaluating the function are given by M(n) = 91 for all integer arguments n ≤ 100, and M(n) = n − 10 for n > 100. Indeed, the result of M(101) is also 91 (101 - 10 = 91). All results of M(n) after n = 101 are continually increasing by 1, e.g. M(102) = 92, M(103) = 93. (en) La fonction 91 de McCarthy est une fonction récursive définie par McCarthy dans son étude de propriétés de programmes récursifs, et notamment de leur vérification formelle. Avec la fonction de Takeuchi, elle est un exemple amplement repris dans les manuels de programmation. (fr) In matematica discreta, la Funzione 91 di McCarthy è una funzione ricorsiva che restituisce 91 per tutti gli argomenti n ≤ 101 e restituisce per . Limitatamente all'insieme degli interi minori di 102 essa, quindi, è un'endofunzione avente un unico punto fisso. Tale funzione fu ideata dall'informatico John McCarthy. La Funzione 91 di McCarthy è definita come segue: Esempi: John McCarthy potrebbe aver scritto in questo modo la funzione, nel linguaggio di programmazione Lisp che lui stesso inventò: : (defun mc91 (n) (cond ((<= n 100) (mc91 (mc91 (+ n 11)))) (t (- n 10)))) (it) マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 n ≤ 101 に対して 91 を返し、n > 101 に対しては を返す。計算機科学者ジョン・マッカーシーが考案した。 マッカーシーの91関数の定義は次の通り。 例 A: M(99) = M(M(110)) 99 ≤ 100 であるため = M(100) 110 > 100 であるため = M(M(111)) 100 ≤ 100 であるため = M(101) 111 > 100 であるため = 91 101 > 100 であるため 例 B: M(87) = M(M(98)) = M(M(M(109))) = M(M(99)) = M(M(M(110))) = M(M(100)) = M(M(M(111))) = M(M(101)) = M(91) = M(M(102)) = M(92) = M(M(103)) = M(93) .... このパターンが続く = M(99) （以下、例 A と同じ） = 91 90 ≤ n < 101 のとき、 (ja) |
| rdfs:label | Función 91 de McCarthy (es) Fonction 91 de McCarthy (fr) Funzione 91 di McCarthy (it) マッカーシーの91関数 (ja) McCarthy 91 function (en) |
| owl:sameAs | freebase:McCarthy 91 function yago-res:McCarthy 91 function wikidata:McCarthy 91 function dbpedia-es:McCarthy 91 function dbpedia-fr:McCarthy 91 function dbpedia-it:McCarthy 91 function dbpedia-ja:McCarthy 91 function https://global.dbpedia.org/id/2rBAe |
| prov:wasDerivedFrom | wikipedia-en:McCarthy_91_function?oldid=1122572514&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:McCarthy_91_function |
| is dbo:wikiPageRedirects of | dbr:McCarthy_91 dbr:Mccarthy_91-function |
| is dbo:wikiPageWikiLink of | dbr:F91 dbr:General_recursive_function dbr:91_(number) dbr:John_McCarthy_(computer_scientist) dbr:McCarthy_91 dbr:Mccarthy_91-function dbr:Recursion_(computer_science) dbr:M91 |
| is foaf:primaryTopic of | wikipedia-en:McCarthy_91_function |