Model of computation
Model of Computation is a formal framework used in Computer Science and Mathematics to describe the computational abilities of a machine. It is a theoretical construct that defines the rules of computation, including the set of allowable operations, the format and type of inputs and outputs, and the speed or cost of operations.
Definition[edit | edit source]
A Model of Computation consists of three main components:
- States: These are the configurations that a machine can be in. For example, in a Turing machine, the state includes the current position of the head, the current state of the machine, and the contents of the tape.
- Transitions: These are the rules that determine how the machine moves from one state to another. In a Turing machine, the transition function takes the current state and the current tape symbol as input and outputs the new state, the new tape symbol, and the direction in which to move the head.
- Start and Accept States: The start state is the state in which the machine begins its computation. The accept states (also known as final or halting states) are the states in which the machine can halt and accept the input.
Types of Models of Computation[edit | edit source]
There are several types of models of computation, each with its own strengths and weaknesses. Some of the most common include:
- Turing Machines: These are the most powerful model of computation, capable of simulating any other model. They are used as the standard against which other models are compared.
- Finite Automata: These are the simplest model of computation, capable of recognizing regular languages.
- Pushdown Automata: These are more powerful than finite automata, capable of recognizing context-free languages.
- Random Access Machines: These are a model of computation that more closely resembles modern computers, with random access memory and a set of basic operations.
Complexity Theory[edit | edit source]
In Complexity Theory, models of computation are used to classify problems based on their computational complexity. The most well-known complexity classes, P and NP, are defined in terms of a deterministic Turing machine and a non-deterministic Turing machine, respectively.
See Also[edit | edit source]
 | This computer science article is a stub. You can help WikiMD by expanding it. |
 | This mathematics-related article is a stub. You can help WikiMD by expanding it. |
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
