Editing Computability Theory (section)

== <span style="color: #FFFFFF;">Understanding</span> ==
Computability is about '''The Limits of Logic'''.

'''1. The Turing Machine (The "Universal" Brain)''':
Alan Turing proved that you don't need a complex brain to do math. All you need is:
1. A way to '''Read''' and '''Write''' a symbol.
2. A way to '''Move''' left or right.
3. A set of '''Rules''' (e.g., "If you see a 1, write a 0 and move left").
Every computer in the world, from your phone to a supercomputer, is just a faster version of this simple machine.

'''2. The "Unsolvable" (The Halting Problem)''':
Turing proved there are "Blind Spots" in math. He showed that you cannot write a "Universal Debugger" that can look at any piece of code and tell if it will crash (run forever) or finish. Why? Because the debugger would eventually have to look at ''itself'', creating a logical paradox like "This sentence is a lie."

'''3. The Hierarchy of Difficulty''':
Not all hard problems are the same.
* '''Decidable''': "Is 7 a prime number?" (Computer says Yes/No).
* '''Recognizable''': "Does this program ever stop?" (If it stops, computer says Yes. If it doesn't, the computer might just run forever and never give an answer).
* '''Undecidable''': "Is this piece of code the shortest possible version of itself?" (No computer can ever answer this for all cases).

'''Kolmogorov Complexity''': This is the "True" size of information. The complexity of a string of text is the length of the ''shortest possible program'' that can generate it. A random string has high complexity (you just have to write the whole thing), while a pattern like "101010..." has low complexity (the program is "Repeat 10").
</div>

<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">