A Problem asking wether a general algorithm given any arbitrary program and it's input will halt or run forever (Lucas, 2021).

​

         HALT = {⟨P,x⟩ | P is a Turing machine and P halts on input x}

​

Turing formulated his T.M "Turing Machine", a concept to prove that the above mentioned problem is only semi-decidable, thus r.e. "recursively enumerable". If machine halts, then x is a member, but to determine if an input is a non member the machine might have to run perpetually, thus never halting. 

 

In essence, Turing and Gödel both employed encodement to transform describable machine or syntax into data (there exist many non describable or unrecognizable). Their method coincides despite diverged formalizations and aims. It is this method of encoding which enabled self reference in both context. 

​

Hence the topic <enumerability> is essential to this EE, despite first glance disparity.

 

 

Acknowledged as “one of the most philosophically important theorems of the theory of computation” [17, Section 4.2].

​

​