About: McCarthy 91 function     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatFormalMethods, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMcCarthy_91_function

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.

AttributesValues
rdf:type
rdfs:label
  • Función 91 de McCarthy (es)
  • Fonction 91 de McCarthy (fr)
  • Funzione 91 di McCarthy (it)
  • マッカーシーの91関数 (ja)
  • McCarthy 91 function (en)
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)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has 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)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 54 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software