Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal denitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of the input bits" [1],[2],[3],[4],[5].
We further develop these results above and we present a formal counter-
part of the intuitive notion "what does the program think " at different
stages of its computation on the processed input word. The denition is
constructed as the logical consequences of the denition of the knowledge
about the contents of input bits above.
Our formal denition is in a good relation to the world of intuitive ideas.
We prove the theorem saying that the programs which are allowed to
compute (think) in a more sophisticated way can compute more effec-
tively. We also demonstrate an example that for some programs a small
enrichment of their inherent logical possibilities implies a dramatic com-
plexity drop. So, our denition lives up to the expectations inspired by
intuition.
The present paper opens a large eld of possible investigations of rela-
tions between logic on one hand and complexity on the other hand.