User:IssaRice/Computability and logic/Motivation for encoding - Revision history

IssaRice at 05:27, 20 August 2019

2019-08-20T05:27:01Z

← Older revision		Revision as of 05:27, 20 August 2019
Line 5:		Line 5:
	* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.		* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.
	* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.		* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.
	* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we get a bunch of interesting diagonalization theorems.		* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we get a bunch of interesting diagonalization theorems, the universal partial recursive function, etc.

IssaRice at 05:26, 20 August 2019

2019-08-20T05:26:38Z

← Older revision		Revision as of 05:26, 20 August 2019
Line 5:		Line 5:
	* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.		* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.
	* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.		* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.
	* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we a bunch of interesting diagonalization theorems.		* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we get a bunch of interesting diagonalization theorems.

IssaRice at 05:25, 20 August 2019

2019-08-20T05:25:20Z

← Older revision		Revision as of 05:25, 20 August 2019
Line 1:		Line 1:
	The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answer is only implicit in the theorems which are presented).		The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answer is only implicit in the theorems which are presented).

	I think the ~~two~~ main reasons are:		I think the three main reasons are:

	* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.		* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.
	* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.		* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.
	* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we a bunch of interesting diagonalization theorems.		* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we a bunch of interesting diagonalization theorems.

IssaRice: Created page with "The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answ..."

2019-08-20T05:24:54Z

Created page with "The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answ..."

New page

The idea of numbering things/encoding things comes up a lot in computability and logic, but many books don't really seem to discuss why we do this in the first place (the answer is only implicit in the theorems which are presented).

I think the two main reasons are:

* Encoding things verifies countability. In general, looking at sets/functions of the natural numbers gives us uncountable objects, but by being able to number all objects of interest, we make sure that our collection is countable.
* Encoding allows for simulation/proving equivalences (allows different formalisms to talk to each other). For instance, we can encode Turing machine configurations using natural numbers, which allows partial recursive functions to simulate Turing machine computations.
* Encoding allows self-reference. Partial recursive functions take as input natural numbers, not other partial recursive functions. Similarly, first order formulas can quantify over natural numbers and do arithmetic, but don't have native access to talking about themselves. By numbering things, we create a way to do self-reference while avoiding the standard paradoxes of self-reference (like Russell's paradox). And once we have self-reference, we a bunch of interesting diagonalization theorems.