It is known from history of mathematics, that Gödel submitted his two incompleteness theorems, which can be considered as one of hallmarks of modern mathematics in 20th century. Here we argue that Gödel incompleteness theorem and its self-referential paradox have not only put Hilbert’s axiomatic program into question, but he also opened up the problem deep inside the then popular Aristotelian Logic. Although there were some attempts to go beyond Aristotelian binary logic, including by Lukasiewicz’s three-valued logic, here we argue that the problem of self-referential paradox can be seen as reconcilable and solvable from Neutrosophic Logic perspective. Motivation of this paper: These authors are motivated to re-describe the self-referential...