#physic #compound-knowledge #fundamental #math #computation Created at 111123 # [Anonymous feedback](https://www.admonymous.co/louis030195) # [[Epistemic status]] #shower-thought Last modified date: 111123 Commit: 0 # Related - [[Fundamental laws of physics]] - [[Fundamental laws of biology]] - [[Theory of evolution]] - [[Theory of knowledge]] # Fundamental laws of computation | Branch | Equation | Description | | ------ | -------- | ----------- | | **Finite Automata (FA)** | - | A model for simple computational machines, can recognize patterns within input obtained from some sort of feed. | | **Context-Free Grammar (CFG)** | - | A set of production rules that describe all possible strings in a given formal language. | | **Turing Machine (TM)** | - | A model of computation that can simulate any algorithm, fundamental to understanding the limits of what can be computed. | | **P (Polynomial Time)** | - | Class of decision problems solvable by a deterministic Turing machine in polynomial time. | | **NP (Nondeterministic Polynomial Time)** | - | Class of decision problems for which a solution can be verified in polynomial time by a nondeterministic Turing machine. | | **NP-Complete** | - | A subset of NP; problems to which all other NP problems can be reduced in polynomial time, and whose solution can be verified in polynomial time. | | **NP-Hard** | - | Problems as hard as the hardest problems in NP, not necessarily in NP themselves. | | **Big O Notation** | $O(n), O(n^2), etc.$ | Notation used to describe the upper bound of the time complexity or space complexity of an algorithm. | | **Church-Turing Thesis** | - | A hypothesis about the nature of computable functions, stating that any function that can be computed by an algorithm can be computed by a Turing machine. | | **Halting Problem** | - | Demonstrates the impossibility of determining, in every case, whether a given program will finish running or continue to run indefinitely. | | **Reduction** | - | A technique for proving one problem is at least as difficult as another by showing how an algorithm for one can be used to solve the other. |