User:IssaRice/Computability and logic/K is recursively enumerable - Revision history

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T21:49:59Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 21:49, 9 January 2019
Line 9:		Line 9:
	'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.		'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.

	We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around. To be more rigorous, I think we need to say that <math>\phi_x(x) = \Phi(x,x)</math>, where <math>\Phi</math> is the two-place universal function. Since the universal function is partial recursive, we can be sure that we can use the expression "<math>\phi_x(x)</math>" and move the index around.)		We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around. To be more rigorous, I think we need to say that <math>\phi_x(x) = \Phi(x,x)</math>, where <math>\Phi</math> is the two-place universal function. Since the universal function is partial recursive, we can be sure that we can use the expression "<math>\phi_x(x)</math>" and move the index around. Even more formally, we can say <math>d = \mathrm{compose}(\Phi; \mathrm{id}^1_1, \mathrm{id}^1_1)</math>.)

	But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.		But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T20:12:12Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 20:12, 9 January 2019
Line 9:		Line 9:
	'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.		'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.

	We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around.)		We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around. To be more rigorous, I think we need to say that <math>\phi_x(x) = \Phi(x,x)</math>, where <math>\Phi</math> is the two-place universal function. Since the universal function is partial recursive, we can be sure that we can use the expression "<math>\phi_x(x)</math>" and move the index around.)

	But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.		But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T20:08:48Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 20:08, 9 January 2019
Line 9:		Line 9:
	'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.		'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.

	We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.		We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around.)

	But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.		But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

IssaRice: /* Using programs */

2019-01-09T20:06:34Z

Using programs

← Older revision		Revision as of 20:06, 9 January 2019
Line 16:		Line 16:

	===Using programs===		===Using programs===

			Peter Smith. An Introduction to Gödel's Theorems. p. 24.

	==References==		==References==

	<references/>		<references/>

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T20:06:18Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 20:06, 9 January 2019
Line 7:		Line 7:
	This proof is from Enderton.<ref>Herbert Enderton. ''Computability Theory''. p. 80</ref>		This proof is from Enderton.<ref>Herbert Enderton. ''Computability Theory''. p. 80</ref>

	Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.		'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.

	We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.		We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T20:05:24Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 20:05, 9 January 2019
Line 12:		Line 12:

	But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.		But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

			'''Discussion.''' The definition of <math>d</math> doesn't seem to be important. Actually, I think we can just take <math>d(x) = \phi_x(x)</math>. But it seems Enderton did the plus one to make a further point (namely, that it ''looks like'' we might be diagonalizing out of this class of functions, but luckily we're not, thanks to our objects only being partial functions).

	===Using programs===		===Using programs===

IssaRice: /* Finding a partial recursive function that enumerates K */

2019-01-09T20:02:23Z

Finding a partial recursive function that enumerates K

← Older revision		Revision as of 20:02, 9 January 2019
Line 11:		Line 11:
	We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.		We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.

	But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.		But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

	===Using programs===		===Using programs===

IssaRice at 20:01, 9 January 2019

2019-01-09T20:01:06Z

← Older revision		Revision as of 20:01, 9 January 2019
Line 14:		Line 14:

	===Using programs===		===Using programs===

			==References==

			<references/>

IssaRice: Created page with " $K := \{x : x \in W_x\}$ ==Proofs== ===Finding a partial recursive function that enumerates ''K''=== This proof is from Enderton.Herbert Enderton. ''Computa..."

2019-01-09T20:00:51Z

Created page with "<math>K := \{x : x \in W_x\}</math> ==Proofs== ===Finding a partial recursive function that enumerates ''K''=== This proof is from Enderton.<ref>Herbert Enderton. ''Computa..."

New page

<math>K := \{x : x \in W_x\}</math>

==Proofs==

===Finding a partial recursive function that enumerates ''K''===

This proof is from Enderton.<ref>Herbert Enderton. ''Computability Theory''. p. 80</ref>

Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.

We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.

But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

===Using programs===

User:IssaRice/Computability and logic/K is recursively enumerable - Revision history

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice: /* Using programs */

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice: /* Finding a partial recursive function that enumerates K */

IssaRice at 20:01, 9 January 2019

IssaRice: Created page with "K := \{x : x \in W_x\} ==Proofs== ===Finding a partial recursive function that enumerates ''K''=== This proof is from Enderton.Herbert Enderton. ''Computa..."

IssaRice: Created page with " $K := \{x : x \in W_x\}$ ==Proofs== ===Finding a partial recursive function that enumerates ''K''=== This proof is from Enderton.Herbert Enderton. ''Computa..."