computation | brain

Maths › 03. Logic and Foundations ›

16. Intuitionistic Logic

Intuitionistic logic studies reasoning in which a statement is accepted only when there is a construction, proof, or method that establishes it. The chapter begins with constructive semantics, where truth is understood through evidence rather than only through truth values, and this changes the interpretation of several familiar logical principles. Proof interpretation is then introduced to explain how formulas correspond to kinds of constructions, so that a proof of a...

Maths › 03. Logic and Foundations ›

13.5 Proof Length and Complexity

13.5 Proof Length and Complexity Proof theory can ask not only whether a formula is provable, but also how hard it is to prove. This leads to the study of proof length and proof complexity. A formal proof is a finite object, so it has a size. We may count the number of lines, the number of inference steps, the total number of symbols, or the size of the proof...

Maths › 03. Logic and Foundations ›

11.2 Computation Traces

11.2 Computation Traces A Turing machine does not compute in one large jump. It computes step by step. A computation trace records these steps. Each step changes the machine from one configuration to the next. A configuration contains all information needed to continue the computation: Component Meaning current state the machine’s internal state tape contents the symbols written on the tape head position the cell currently being scanned Once these...

Maths › 03. Logic and Foundations ›

11.3 Universal Machines

11.3 Universal Machines A universal Turing machine is a Turing machine that can simulate other Turing machines. This is one of the most important ideas in computability theory. It means that computation can be represented as data. A machine can be written down, encoded as a string, and given as input to another machine. In ordinary programming terms, a universal machine is like an interpreter. It receives two things: $$...

Maths › 03. Logic and Foundations ›

11.1 Machine Definitions

11.1 Machine Definitions A Turing machine is a formal model of an algorithm. It describes computation using a finite set of rules and an unbounded tape. The machine has three main parts: Part Role Tape stores symbols Head reads and writes one cell at a time Finite control stores the current state The tape is divided into cells: $$ \cdots,\ c_{-2},\ c_{-1},\ c_0,\ c_1,\ c_2,\ \cdots $$ Each cell contains...

Maths › 03. Logic and Foundations ›

10. Computable Functions

Computability theory studies which functions can be calculated by a precise mechanical procedure, and it gives a mathematical meaning to the informal idea of an effective algorithm. The chapter begins with recursive functions, where computation is described by basic initial functions together with operations that generate more complex functions, such as composition, primitive recursion, and minimization. Partial and total functions are then distinguished, since some computations produce an output for...