Boolean functions and computation models

The foundations of computational complexity theory trace back to Alan Turing in the 1930s, who explored automatic procedures for determining the validity of mathematical statements. A key problem in this field is the undecidability of the Halting Problem, which questions whether a given computer program will eventually halt. Today, computational complexity examines the quantitative aspects of solutions: Is a problem tractable? To measure intractability, various ideas emerged. A. Cobham questioned the appropriate model for defining a "computation step," M. Rabin proposed axioms for complexity measures, and C. Shannon introduced the boolean circuit for computing boolean functions. A crucial inquiry persists: What is the essence of computation? In 1957, John von Neumann noted in his Silliman Lectures that logics and statistics should be viewed as fundamental tools of information theory. He emphasized that the experience surrounding the planning, evaluating, and coding of complex logical and mathematical automata would significantly inform information theory, particularly regarding large electronic computing machines, which are the most typical, though not the only, examples of such automata.