User:IssaRice/Computability and logic/Function versus algorithm - Revision history

IssaRice: /* Algorithm as index */

2019-02-04T19:33:10Z

Algorithm as index

← Older revision		Revision as of 19:33, 4 February 2019
Line 10:		Line 10:
	If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.		If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.

	If we define a function in some exotic way that makes use of something outside our formal definition of computable partial functions, then you won't find the same description in the enumeration, but you will still find the partial function in the enumeration (assuming the partial function can be computed). A silly example that illustrates the point: if we define <math>f(n)</math> to be the number of times Socrates blinked on day <math>n</math> of his life, then this function is computable since we just have to store some finite list of numbers. But you won't be able to find this description of the definition of <math>f</math> in our enumeration. Instead, in the simplest case, you will find a description that looks like a bunch of case statements (if <math>n = 0</math> output <math>n_0</math>; else if <math>n = 1</math> output <math>n_1</math>; else if ...). You might also find something that looks like a simulation of the life of Socrates, with hair-counting devices on each day.		If we define a function in some exotic way that makes use of something outside our formal definition of computable partial functions, then you won't find the same description in the enumeration, but you will still find the partial function in the enumeration (assuming the partial function can be computed). A silly example that illustrates the point: if we define <math>f(n)</math> to be the number of times Socrates blinked on day <math>n</math> of his life, then this function is computable since we just have to store some finite list of numbers. But you won't be able to find this description of the definition of <math>f</math> in our enumeration. Instead, in the simplest case, you will find a description that looks like a bunch of case statements (if <math>n = 0</math> output <math>n_0</math>; else if <math>n = 1</math> output <math>n_1</math>; else if ...). You might also find something that looks like a simulation of the life of Socrates, with hair-counting devices recording the function value on each day.

IssaRice: /* Algorithm as index */

2019-02-04T19:32:12Z

Algorithm as index

← Older revision		Revision as of 19:32, 4 February 2019
Line 10:		Line 10:
	If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.		If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.

	If we define a function in some exotic way that makes use of something outside our formal definition of computable partial functions, then you won't find the same description in the enumeration, but you will still find the partial function in the enumeration (assuming the partial function can be computed).		If we define a function in some exotic way that makes use of something outside our formal definition of computable partial functions, then you won't find the same description in the enumeration, but you will still find the partial function in the enumeration (assuming the partial function can be computed). A silly example that illustrates the point: if we define <math>f(n)</math> to be the number of times Socrates blinked on day <math>n</math> of his life, then this function is computable since we just have to store some finite list of numbers. But you won't be able to find this description of the definition of <math>f</math> in our enumeration. Instead, in the simplest case, you will find a description that looks like a bunch of case statements (if <math>n = 0</math> output <math>n_0</math>; else if <math>n = 1</math> output <math>n_1</math>; else if ...). You might also find something that looks like a simulation of the life of Socrates, with hair-counting devices on each day.

IssaRice: /* Algorithm as index */

2019-02-04T19:23:08Z

Algorithm as index

← Older revision		Revision as of 19:23, 4 February 2019
Line 9:		Line 9:

	If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.		If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.

			If we define a function in some exotic way that makes use of something outside our formal definition of computable partial functions, then you won't find the same description in the enumeration, but you will still find the partial function in the enumeration (assuming the partial function can be computed).

IssaRice: /* Algorithm as index */

2019-02-04T19:14:42Z

Algorithm as index

← Older revision		Revision as of 19:14, 4 February 2019
Line 8:		Line 8:
	==Algorithm as index==		==Algorithm as index==

	If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.		If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some computable partial function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.

IssaRice at 19:13, 4 February 2019

2019-02-04T19:13:22Z

← Older revision		Revision as of 19:13, 4 February 2019
Line 5:		Line 5:
	* Each algorithms computes exactly one function		* Each algorithms computes exactly one function
	* Each computable partial function has many different algorithms that compute it		* Each computable partial function has many different algorithms that compute it

			==Algorithm as index==

			If we want to enumerate all of the computable partial functions (say, in order to do some diagonalization argument) the usual way to do this is to enumerate all of the algorithms first, encode the algorithm as an index, and then use this enumeration as an enumeration of the computable partial functions. What this means is that when we refer to some computable partial function as <math>\phi_k</math>, for example, then actually we know more than just what the function is: we also know that <math>k</math> is an integer that encodes the algorithm that computes <math>\phi_k</math>. In contrast, if we just had some function called <math>f</math>, then we know that ''some'' algorithm computes <math>f</math>, but we have no name for it/a canonical choice for it, so we have to pick some number, say, <math>n</math>, so that <math>f = \phi_n</math>.

IssaRice at 19:06, 4 February 2019

2019-02-04T19:06:19Z

← Older revision		Revision as of 19:06, 4 February 2019
Line 1:		Line 1:
	~~write this later~~.		In computability theory, a distinction is made between algorithms and functions.

			==Mapping between algorithms and computable partial functions==

			* Each algorithms computes exactly one function
			* Each computable partial function has many different algorithms that compute it

IssaRice: Created page with "write this later."

2018-12-18T07:07:07Z

Created page with "write this later."

New page

write this later.