[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/turing_machine.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "turing machine (overview)" type: concept related: [Turing Machinea, Diagonalization Argument, Universal Turing Machine, Mapping Reduction, Kolomogorov Complexity] source: https://www.jemoka.com/posts/kbhturing_machine/ confidence: high status: active --- turing machine is a computational system that has a memory tape, and can go through the input multiple times; they don’t have to accept or reject states, turing machines can run forever and can have loops. For the main topic, see turing machine decidable vs. recognizable languages there are not enough Turing Machines to compute every language (so there are non-recognizable/non-decidable languages) halting problem and ATM, meaning strings where Turing Machines can’t decide them “the diagonalization argument” mapping reduction Rice’s Theorem strong reduction: higher achy of hard problems self-reference turing Machines can view and produce its own code. foundations of mathematics can be shown using these systems Kolomogorov Complexity see Kolomogorov Complexity Non-deterministic Turing Machine They are not really good computational system, non-determinism doesn’t add that much power by normal Turing Machine. Encodeable Turing Machines For every Turing Machine, we can encode it into a string. We can, for instance, use a turing machine to generate another turing machine. This also allows us to make universal turing machines—using Turing machines to simulate anotherr turing machines.