Computability Theory - Revision history

Wordpad: BloomWiki: Computability Theory

2026-04-25T01:49:04Z

BloomWiki: Computability Theory

← Older revision		Revision as of 01:49, 25 April 2026
Line 1:		Line 1:
			<div style="background-color: #4B0082; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
	{{BloomIntro}}		{{BloomIntro}}
	Computability Theory (also known as Recursion Theory) is the branch of mathematical logic and computer science that explores which problems can be solved by an algorithm and which cannot. While we often think of computers as "Omnipotent," computability theory proves that there are mathematical questions that no computer—no matter how powerful or how much time it has—can ever answer. It is the study of the '''Boundaries of the Calculable'''. By understanding these limits, we can focus our efforts on "Decidable" problems and understand the fundamental nature of information and intelligence.		Computability Theory (also known as Recursion Theory) is the branch of mathematical logic and computer science that explores which problems can be solved by an algorithm and which cannot. While we often think of computers as "Omnipotent," computability theory proves that there are mathematical questions that no computer—no matter how powerful or how much time it has—can ever answer. It is the study of the '''Boundaries of the Calculable'''. By understanding these limits, we can focus our efforts on "Decidable" problems and understand the fundamental nature of information and intelligence.
			</div>

	== Remembering ==		__TOC__

			<div style="background-color: #000080; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Remembering</span> ==
	* '''Computability Theory''' — The study of the mathematical limits of computation.		* '''Computability Theory''' — The study of the mathematical limits of computation.
	* '''Algorithm''' — A step-by-step procedure for solving a problem.		* '''Algorithm''' — A step-by-step procedure for solving a problem.
Line 16:		Line 21:
	* '''Rice's Theorem''' — A theorem stating that ''any'' non-trivial property of a program's behavior is undecidable.		* '''Rice's Theorem''' — A theorem stating that ''any'' non-trivial property of a program's behavior is undecidable.
	* '''Busy Beaver''' — A game to find the simplest program that runs for the longest possible time before stopping.		* '''Busy Beaver''' — A game to find the simplest program that runs for the longest possible time before stopping.
			</div>

	== Understanding ==		<div style="background-color: #006400; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Understanding</span> ==
	Computability is about '''The Limits of Logic'''.		Computability is about '''The Limits of Logic'''.

Line 37:		Line 44:

	'''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").		'''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>

	== Applying ==		<div style="background-color: #8B0000; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Applying</span> ==
	'''Modeling 'The Halting Problem' Logic (The Paradox):'''		'''Modeling 'The Halting Problem' Logic (The Paradox):'''
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
Line 67:		Line 76:
	: '''Wang Tiles''' → A set of colored tiles that can "compute" anything; if you can tile a floor with them, you can build a computer.		: '''Wang Tiles''' → A set of colored tiles that can "compute" anything; if you can tile a floor with them, you can build a computer.
	: '''Game of Life''' → A simple simulation that is "Turing Complete," meaning a simulated "Life" world could theoretically run its own version of Windows.		: '''Game of Life''' → A simple simulation that is "Turing Complete," meaning a simulated "Life" world could theoretically run its own version of Windows.
			</div>

	== Analyzing ==		<div style="background-color: #8B4500; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Analyzing</span> ==
	{\| class="wikitable"		{\| class="wikitable"
	\|+ Computable vs. Non-Computable		\|+ Computable vs. Non-Computable
Line 83:		Line 94:

	'''The Concept of "Reduction"''': This is how computer scientists solve problems. If you have a new problem, you try to "Reduce" it to an old one. "If I can solve X, I can solve Y." If we can reduce the Halting Problem to your problem, then your problem is also unsolvable. Analyzing these "Chains of Difficulty" is the core of computability theory.		'''The Concept of "Reduction"''': This is how computer scientists solve problems. If you have a new problem, you try to "Reduce" it to an old one. "If I can solve X, I can solve Y." If we can reduce the Halting Problem to your problem, then your problem is also unsolvable. Analyzing these "Chains of Difficulty" is the core of computability theory.
			</div>

	== Evaluating ==		<div style="background-color: #483D8B; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Evaluating</span> ==
	Evaluating an algorithm's limits:		Evaluating an algorithm's limits:
	# '''Decidability''': Is there a "Stop" button that always works?		# '''Decidability''': Is there a "Stop" button that always works?
Line 90:		Line 103:
	# '''Space Complexity''': Does the calculation require more atoms than exist in the universe?		# '''Space Complexity''': Does the calculation require more atoms than exist in the universe?
	# '''Approximation''': If the perfect answer is uncomputable, can we find an answer that is 99% correct?		# '''Approximation''': If the perfect answer is uncomputable, can we find an answer that is 99% correct?
			</div>

	== Creating ==		<div style="background-color: #2F4F4F; color: #FFFFFF; padding: 20px; border-radius: 8px; margin-bottom: 15px;">
			== <span style="color: #FFFFFF;">Creating</span> ==
	Future Frontiers:		Future Frontiers:
	# '''Quantum Computability''': Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster).		# '''Quantum Computability''': Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster).
Line 101:		Line 116:
	[[Category:Computer Science]]		[[Category:Computer Science]]
	[[Category:Logic]]		[[Category:Logic]]
			</div>

Wordpad: BloomWiki: Computability Theory

2026-04-23T14:38:25Z

BloomWiki: Computability Theory

← Older revision		Revision as of 14:38, 23 April 2026
Line 85:		Line 85:

	== Evaluating ==		== Evaluating ==
	Evaluating an algorithm's limits: ~~(1)~~ '''Decidability''': Is there a "Stop" button that always works? ~~(2)~~ '''Time Complexity''': Even if it's computable, will it take longer than the life of the universe (e.g., Breaking a 2048-bit key)? ~~(3)~~ '''Space Complexity''': Does the calculation require more atoms than exist in the universe? ~~(4)~~ '''Approximation''': If the perfect answer is uncomputable, can we find an answer that is 99% correct?		Evaluating an algorithm's limits:
			# '''Decidability''': Is there a "Stop" button that always works?
			# '''Time Complexity''': Even if it's computable, will it take longer than the life of the universe (e.g., Breaking a 2048-bit key)?
			# '''Space Complexity''': Does the calculation require more atoms than exist in the universe?
			# '''Approximation''': If the perfect answer is uncomputable, can we find an answer that is 99% correct?

	== Creating ==		== Creating ==
	Future Frontiers: ~~(1)~~ '''Quantum Computability''': Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster). ~~(2)~~ '''Hyper-computation''': The theoretical search for physical systems (like black holes) that might be able to compute more than a Turing Machine. ~~(3)~~ '''Bio-Computation''': Using DNA or cells to perform "Parallel" computations that are hard for silicon. ~~(4)~~ '''AI Autonomy''': The debate over whether a machine can ever "Compute" consciousness, or if consciousness is non-computable.		Future Frontiers:
			# '''Quantum Computability''': Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster).
			# '''Hyper-computation''': The theoretical search for physical systems (like black holes) that might be able to compute more than a Turing Machine.
			# '''Bio-Computation''': Using DNA or cells to perform "Parallel" computations that are hard for silicon.
			# '''AI Autonomy''': The debate over whether a machine can ever "Compute" consciousness, or if consciousness is non-computable.

	[[Category:Mathematics]]		[[Category:Mathematics]]
	[[Category:Computer Science]]		[[Category:Computer Science]]
	[[Category:Logic]]		[[Category:Logic]]

Wordpad: BloomWiki: Computability Theory

2026-04-23T14:29:12Z

BloomWiki: Computability Theory

Wordpad: BloomWiki: Computability Theory

2026-04-23T14:23:19Z

BloomWiki: Computability Theory

← Older revision		Revision as of 14:23, 23 April 2026
Line 1:		Line 1:
	{{BloomIntro}}		{{BloomIntro}}
	Computability Theory (also known as Recursion Theory) is the branch of mathematical logic and computer science that explores which problems can be solved by an algorithm and which cannot. While we often think of computers as "Omnipotent," computability theory proves that there are mathematical questions that no computer—no matter how powerful or how much time it has—can ever answer. It is the study of the Boundaries of the Calculable. By understanding these limits, we can focus our efforts on "Decidable" problems and understand the fundamental nature of information and intelligence.		Computability Theory (also known as Recursion Theory) is the branch of mathematical logic and computer science that explores which problems can be solved by an algorithm and which cannot. While we often think of computers as "Omnipotent," computability theory proves that there are mathematical questions that no computer—no matter how powerful or how much time it has—can ever answer. It is the study of the '''Boundaries of the Calculable'''. By understanding these limits, we can focus our efforts on "Decidable" problems and understand the fundamental nature of information and intelligence.

	== Remembering ==		== Remembering ==
Line 18:		Line 18:

	== Understanding ==		== Understanding ==
	Computability is about The Limits of Logic.		Computability is about '''The Limits of Logic'''.

	1. The Turing Machine (The "Universal" Brain):		'''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:		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.		1. A way to '''Read''' and '''Write''' a symbol.
	2. A way to Move left or right.		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").		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.		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):		'''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."		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:		'''3. The Hierarchy of Difficulty''':
	Not all hard problems are the same.		Not all hard problems are the same.
	* Decidable: "Is 7 a prime number?" (Computer says Yes/No).		* '''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).		* '''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).		* '''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").		'''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").

	== Applying ==		== Applying ==
Line 82:		Line 82:
	\|}		\|}

	The Concept of "Reduction": This is how computer scientists solve problems. If you have a new problem, you try to "Reduce" it to an old one. "If I can solve X, I can solve Y." If we can reduce the Halting Problem to your problem, then your problem is also unsolvable. Analyzing these "Chains of Difficulty" is the core of computability theory.		'''The Concept of "Reduction"''': This is how computer scientists solve problems. If you have a new problem, you try to "Reduce" it to an old one. "If I can solve X, I can solve Y." If we can reduce the Halting Problem to your problem, then your problem is also unsolvable. Analyzing these "Chains of Difficulty" is the core of computability theory.

	== Evaluating ==		== Evaluating ==
	Evaluating an algorithm's limits: (1) Decidability: Is there a "Stop" button that always works? (2) Time Complexity: Even if it's computable, will it take longer than the life of the universe (e.g., Breaking a 2048-bit key)? (3) Space Complexity: Does the calculation require more atoms than exist in the universe? (4) Approximation: If the perfect answer is uncomputable, can we find an answer that is 99% correct?		Evaluating an algorithm's limits: (1) '''Decidability''': Is there a "Stop" button that always works? (2) '''Time Complexity''': Even if it's computable, will it take longer than the life of the universe (e.g., Breaking a 2048-bit key)? (3) '''Space Complexity''': Does the calculation require more atoms than exist in the universe? (4) '''Approximation''': If the perfect answer is uncomputable, can we find an answer that is 99% correct?

	== Creating ==		== Creating ==
	Future Frontiers: (1) Quantum Computability: Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster). (2) Hyper-computation: The theoretical search for physical systems (like black holes) that might be able to compute more than a Turing Machine. (3) Bio-Computation: Using DNA or cells to perform "Parallel" computations that are hard for silicon. (4) AI Autonomy: The debate over whether a machine can ever "Compute" consciousness, or if consciousness is non-computable.		Future Frontiers: (1) '''Quantum Computability''': Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster). (2) '''Hyper-computation''': The theoretical search for physical systems (like black holes) that might be able to compute more than a Turing Machine. (3) '''Bio-Computation''': Using DNA or cells to perform "Parallel" computations that are hard for silicon. (4) '''AI Autonomy''': The debate over whether a machine can ever "Compute" consciousness, or if consciousness is non-computable.

	[[Category:Mathematics]]		[[Category:Mathematics]]
	[[Category:Computer Science]]		[[Category:Computer Science]]
	[[Category:Logic]]		[[Category:Logic]]

Wordpad: BloomWiki: Computability Theory

2026-04-23T13:53:02Z

BloomWiki: Computability Theory

New page

{{BloomIntro}}
Computability Theory (also known as Recursion Theory) is the branch of mathematical logic and computer science that explores which problems can be solved by an algorithm and which cannot. While we often think of computers as "Omnipotent," computability theory proves that there are mathematical questions that no computer—no matter how powerful or how much time it has—can ever answer. It is the study of the **Boundaries of the Calculable**. By understanding these limits, we can focus our efforts on "Decidable" problems and understand the fundamental nature of information and intelligence.

== Remembering ==
* '''Computability Theory''' — The study of the mathematical limits of computation.
* '''Algorithm''' — A step-by-step procedure for solving a problem.
* '''Turing Machine''' — A theoretical model of a computer consisting of an infinite tape and a read/write head (The "Gold Standard" for what is computable).
* '''Decidability''' — A property of a problem that can be solved with a "Yes/No" answer by an algorithm in finite time.
* '''Recursively Enumerable''' — A set where a computer can list all the elements, but might never finish.
* '''The Halting Problem''' — The famous proof that you cannot write a program that can tell if *any* other program will eventually stop or run forever.
* '''Church-Turing Thesis''' — The hypothesis that any problem that can be solved by a "Human with a pencil" can be solved by a Turing Machine.
* '''P vs. NP''' — The most famous unsolved problem: "If a solution is easy to check, is it also easy to find?"
* '''Turing Completeness''' — A system is Turing Complete if it can simulate any Turing Machine (e.g., Python, C++, and even some video games like Minecraft).
* '''Undecidable Problem''' — A problem for which it is mathematically impossible to construct an algorithm that always leads to a correct yes-or-no answer.
* '''Oracle Machine''' — A theoretical computer that has access to a "Magic Box" that can solve one specific undecidable problem instantly.
* '''Rice's Theorem''' — A theorem stating that *any* non-trivial property of a program's behavior is undecidable.
* '''Busy Beaver''' — A game to find the simplest program that runs for the longest possible time before stopping.

== Understanding ==
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").

== Applying ==
'''Modeling 'The Halting Problem' Logic (The Paradox):'''
<syntaxhighlight lang="python">
def hypothetical_halt_checker(program_code):
"""
Turing proved this function CANNOT EXIST.
If it did, we could create a paradox.
"""
pass

def paradox_program(code):
"""
If the checker says I will HALT, I will run forever.
If the checker says I will RUN FOREVER, I will halt.
"""
if hypothetical_halt_checker(code) == "HALTS":
while True: pass # Run forever
else:
return "HALTED"

# This logical 'Loop' proves that the checker can
# never be 100% correct for all programs.
</syntaxhighlight>

; Computability Milestones
: '''The Entscheidungsproblem''' → The "Decision Problem" that Turing and Church solved, proving math is not fully decidable.
: '''Lambda Calculus''' → Alonzo Church's version of computability, which is the basis for "Functional" programming languages like Haskell and Lisp.
: '''Wang Tiles''' → A set of colored tiles that can "compute" anything; if you can tile a floor with them, you can build a computer.
: '''Game of Life''' → A simple simulation that is "Turing Complete," meaning a simulated "Life" world could theoretically run its own version of Windows.

== Analyzing ==
{| class="wikitable"
|+ Computable vs. Non-Computable
! Feature !! Computable (Sorting a list) !! Non-Computable (Shortest program)
|-
| Logic || Follows a finite set of steps || Requires 'Infinite' knowledge or luck
|-
| Outcome || Guaranteed answer || No algorithm exists
|-
| Machine || Standard computer (Turing Machine) || Requires an 'Oracle'
|-
| Analogy || Following a recipe || Deciding if a poem is 'Perfect'
|}

**The Concept of "Reduction"**: This is how computer scientists solve problems. If you have a new problem, you try to "Reduce" it to an old one. "If I can solve X, I can solve Y." If we can reduce the Halting Problem to your problem, then your problem is also unsolvable. Analyzing these "Chains of Difficulty" is the core of computability theory.

== Evaluating ==
Evaluating an algorithm's limits: (1) **Decidability**: Is there a "Stop" button that always works? (2) **Time Complexity**: Even if it's computable, will it take longer than the life of the universe (e.g., Breaking a 2048-bit key)? (3) **Space Complexity**: Does the calculation require more atoms than exist in the universe? (4) **Approximation**: If the perfect answer is uncomputable, can we find an answer that is 99% correct?

== Creating ==
Future Frontiers: (1) **Quantum Computability**: Do quantum computers make "Unsolvable" problems solvable? (The answer is usually 'No', they just make some solvable ones much faster). (2) **Hyper-computation**: The theoretical search for physical systems (like black holes) that might be able to compute more than a Turing Machine. (3) **Bio-Computation**: Using DNA or cells to perform "Parallel" computations that are hard for silicon. (4) **AI Autonomy**: The debate over whether a machine can ever "Compute" consciousness, or if consciousness is non-computable.

[[Category:Mathematics]]
[[Category:Computer Science]]
[[Category:Logic]]

← Older revision		Revision as of 14:29, 23 April 2026
Line 8:		Line 8:
	* '''Decidability''' — A property of a problem that can be solved with a "Yes/No" answer by an algorithm in finite time.		* '''Decidability''' — A property of a problem that can be solved with a "Yes/No" answer by an algorithm in finite time.
	* '''Recursively Enumerable''' — A set where a computer can list all the elements, but might never finish.		* '''Recursively Enumerable''' — A set where a computer can list all the elements, but might never finish.
	* '''The Halting Problem''' — The famous proof that you cannot write a program that can tell if any other program will eventually stop or run forever.		* '''The Halting Problem''' — The famous proof that you cannot write a program that can tell if ''any'' other program will eventually stop or run forever.
	* '''Church-Turing Thesis''' — The hypothesis that any problem that can be solved by a "Human with a pencil" can be solved by a Turing Machine.		* '''Church-Turing Thesis''' — The hypothesis that any problem that can be solved by a "Human with a pencil" can be solved by a Turing Machine.
	* '''P vs. NP''' — The most famous unsolved problem: "If a solution is easy to check, is it also easy to find?"		* '''P vs. NP''' — The most famous unsolved problem: "If a solution is easy to check, is it also easy to find?"
Line 14:		Line 14:
	* '''Undecidable Problem''' — A problem for which it is mathematically impossible to construct an algorithm that always leads to a correct yes-or-no answer.		* '''Undecidable Problem''' — A problem for which it is mathematically impossible to construct an algorithm that always leads to a correct yes-or-no answer.
	* '''Oracle Machine''' — A theoretical computer that has access to a "Magic Box" that can solve one specific undecidable problem instantly.		* '''Oracle Machine''' — A theoretical computer that has access to a "Magic Box" that can solve one specific undecidable problem instantly.
	* '''Rice's Theorem''' — A theorem stating that any non-trivial property of a program's behavior is undecidable.		* '''Rice's Theorem''' — A theorem stating that ''any'' non-trivial property of a program's behavior is undecidable.
	* '''Busy Beaver''' — A game to find the simplest program that runs for the longest possible time before stopping.		* '''Busy Beaver''' — A game to find the simplest program that runs for the longest possible time before stopping.

Line 28:		Line 28:

	'''2. The "Unsolvable" (The Halting Problem)''':		'''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."		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''':		'''3. The Hierarchy of Difficulty''':
Line 36:		Line 36:
	* '''Undecidable''': "Is this piece of code the shortest possible version of itself?" (No computer can ever answer this for all cases).		* '''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").		'''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").

	== Applying ==		== Applying ==