User:IssaRice/Computability and logic/Diagonalization out of a class: Difference between revisions

From Machinelearning
(Created page with "'''Diagonalization out of a class''' is a trick used to define a function that is not in a given list of functions. Let <math>C</math> be some class of total functions. If we...")
 
No edit summary
 
Line 1: Line 1:
'''Diagonalization out of a class''' is a trick used to define a function that is not in a given list of functions.
'''Diagonalization out of a class''' is a trick used to define a function that is not in a given list of functions.


Let <math>C</math> be some class of total functions. If we are given an enumeration of <math>C</math> such as <math>f_0, f_1, f_2, f_3, \ldots</math> then we can define a new total function <math>g(x) := f_x(x) + 1</math>. Now given any <math>n \in \mathbf N</math>, we have <math>f_n(n) \ne f_n(n) + 1 = g(n)</math>. Thus, <math>g\ne f_n</math> for every <math>n\in \mathbf N</math>, so <math>g\ne C</math>.
Let <math>C</math> be some class of total functions. If we are given an enumeration of <math>C</math> such as <math>f_0, f_1, f_2, f_3, \ldots</math> then we can define a new total function <math>g(x) := f_x(x) + 1</math>. Now given any <math>n \in \mathbf N</math>, we have <math>f_n(n) \ne f_n(n) + 1 = g(n)</math>. Thus, <math>g\ne f_n</math> for every <math>n\in \mathbf N</math>, so <math>g\notin C</math>.

Latest revision as of 06:47, 18 December 2018

Diagonalization out of a class is a trick used to define a function that is not in a given list of functions.

Let C be some class of total functions. If we are given an enumeration of C such as f0,f1,f2,f3,… then we can define a new total function g(x):=fx(x)+1. Now given any n∈N, we have fn(n)≠fn(n)+1=g(n). Thus, g≠fn for every n∈N, so g∉C.

Retrieved from "https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/Diagonalization_out_of_a_class&oldid=1129"