User:IssaRice/Computability and logic/Characterization of recursively enumerable sets - Revision history

IssaRice at 08:54, 26 April 2019

2019-04-26T08:54:39Z

← Older revision		Revision as of 08:54, 26 April 2019
Line 13:		Line 13:
	\| <math>S</math> is empty or the range of a primitive recursive function. \|\| Recursively enumerable		\| <math>S</math> is empty or the range of a primitive recursive function. \|\| Recursively enumerable
	\|-		\|-
	\| <math>S</math> is the domain of a computable partial function. \|\| "Semi"-ness		\| <math>S</math> is the domain of a computable partial function. \|\| Semi-ness
	\|-		\|-
	\| A recursive semicharacteristic function for <math>S</math> exists. \|\| "Semi"-ness		\| A recursive semicharacteristic function for <math>S</math> exists. \|\| Semi-ness
	\|-		\|-
	\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| "Semi"-ness		\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| Semi-ness
	\|-		\|-
	\| The relation <math>x \in S</math> is <math>\Sigma_1</math>, i.e., there exists a <math>(k+1)</math>-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t_1 \cdots \exists t_k\ R(x,t_1,\ldots,t_k)</math> \|\| "Semi"-ness		\| The relation <math>x \in S</math> is <math>\Sigma_1</math>, i.e., there exists a <math>(k+1)</math>-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t_1 \cdots \exists t_k\ R(x,t_1,\ldots,t_k)</math> \|\| Semi-ness
	\|-		\|-
	\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness		\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| Semi-ness
	\|}		\|}

	The rows labeled "Recursively enumerable" all emphasize the fact that <math>S</math> is "recursively enumerable", i.e., that the elements of <math>S</math> can be listed in a recursive (computable) way.		The rows labeled "Recursively enumerable" all emphasize the fact that <math>S</math> is "recursively enumerable", i.e., that the elements of <math>S</math> can be listed in a recursive (computable) way.

	The rows labeled '"Semi"-ness' all emphasize the fact that <math>S</math> is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in <math>S</math>, then in a finite amount of time we can verify this computably, but that if something isn't in <math>S</math>, then we will run into an infinite loop.		The rows labeled "Semi-ness" all emphasize the fact that <math>S</math> is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in <math>S</math>, then in a finite amount of time we can verify this computably, but that if something isn't in <math>S</math>, then we will run into an infinite loop.

	The fundamental theorem of recursively enumerable sets says that recursively enumerable equals "semi"-ness.		The fundamental theorem of recursively enumerable sets says that recursively enumerable equals semi-ness.

	==References==		==References==

	<references/>		<references/>

IssaRice: IssaRice moved page User:IssaRice/Characterization of recursively enumerable sets to User:IssaRice/Computability and logic/Characterization of recursively enumerable sets

2018-12-18T06:25:45Z

IssaRice moved page User:IssaRice/Characterization of recursively enumerable sets to User:IssaRice/Computability and logic/Characterization of recursively enumerable sets

← Older revision	Revision as of 06:25, 18 December 2018
(No difference)

IssaRice at 04:40, 18 December 2018

2018-12-18T04:40:59Z

← Older revision		Revision as of 04:40, 18 December 2018
Line 19:		Line 19:
	\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| "Semi"-ness		\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| "Semi"-ness
	\|-		\|-
	\| The relation <math>x \in S</math> is <math>\Sigma_1</math>, i.e., there exists a <math>(k+1)</math>-place recursive ~~function~~ <math>R</math> such that <math>x \in S \iff \exists t_1 \cdots \exists t_k\ R(x,t_1,\ldots,t_k)</math> \|\| "Semi"-ness		\| The relation <math>x \in S</math> is <math>\Sigma_1</math>, i.e., there exists a <math>(k+1)</math>-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t_1 \cdots \exists t_k\ R(x,t_1,\ldots,t_k)</math> \|\| "Semi"-ness
	\|-		\|-
	\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness		\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness

IssaRice at 04:40, 18 December 2018

2018-12-18T04:40:42Z

← Older revision		Revision as of 04:40, 18 December 2018
Line 19:		Line 19:
	\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| "Semi"-ness		\| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> \|\| "Semi"-ness
	\|-		\|-
	\| The relation <math>x \in S</math> is <math>\Sigma_1</math> \|\| "Semi"-ness		\| The relation <math>x \in S</math> is <math>\Sigma_1</math>, i.e., there exists a <math>(k+1)</math>-place recursive function <math>R</math> such that <math>x \in S \iff \exists t_1 \cdots \exists t_k\ R(x,t_1,\ldots,t_k)</math> \|\| "Semi"-ness
	\|-		\|-
	\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness		\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness

IssaRice at 04:36, 18 December 2018

2018-12-18T04:36:54Z

← Older revision		Revision as of 04:36, 18 December 2018
Line 27:		Line 27:

	The rows labeled '"Semi"-ness' all emphasize the fact that <math>S</math> is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in <math>S</math>, then in a finite amount of time we can verify this computably, but that if something isn't in <math>S</math>, then we will run into an infinite loop.		The rows labeled '"Semi"-ness' all emphasize the fact that <math>S</math> is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in <math>S</math>, then in a finite amount of time we can verify this computably, but that if something isn't in <math>S</math>, then we will run into an infinite loop.

			The fundamental theorem of recursively enumerable sets says that recursively enumerable equals "semi"-ness.

	==References==		==References==

	<references/>		<references/>

IssaRice at 04:36, 18 December 2018

2018-12-18T04:36:06Z

← Older revision		Revision as of 04:36, 18 December 2018
Line 23:		Line 23:
	\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness		\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness
	\|}		\|}

			The rows labeled "Recursively enumerable" all emphasize the fact that <math>S</math> is "recursively enumerable", i.e., that the elements of <math>S</math> can be listed in a recursive (computable) way.

			The rows labeled '"Semi"-ness' all emphasize the fact that <math>S</math> is semidecidable/recognizable/verifiable/semirecursive, i.e., that if something is in <math>S</math>, then in a finite amount of time we can verify this computably, but that if something isn't in <math>S</math>, then we will run into an infinite loop.

	==References==		==References==

	<references/>		<references/>

IssaRice at 04:33, 18 December 2018

2018-12-18T04:33:30Z

← Older revision		Revision as of 04:33, 18 December 2018
Line 23:		Line 23:
	\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness		\| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> \|\| "Semi"-ness
	\|}		\|}

			==References==

			<references/>

IssaRice: Created page with "Let $S$ be a set of natural numbers. The following are all equivalent. {| class="sortable wikitable" |- ! Property !! Emphasis |- | The elements of $S$ ..."

2018-12-18T04:32:59Z

Created page with "Let <math>S</math> be a set of natural numbers. The following are all equivalent. {| class="sortable wikitable" |- ! Property !! Emphasis |- | The elements of <math>S</math>..."

New page

Let <math>S</math> be a set of natural numbers. The following are all equivalent.

{| class="sortable wikitable"
|-
! Property !! Emphasis
|-
| The elements of <math>S</math> can be enumerated in a computable manner as <math>a_0, a_1, a_2, \ldots</math> || Recursively enumerable
|-
| <math>S</math> is the range of a computable partial function. || Recursively enumerable
|-
| <math>S</math> is empty or the range of a computable total function. || Recursively enumerable
|-
| <math>S</math> is empty or the range of a primitive recursive function. || Recursively enumerable
|-
| <math>S</math> is the domain of a computable partial function. || "Semi"-ness
|-
| A recursive semicharacteristic function for <math>S</math> exists. || "Semi"-ness
|-
| There exists a two-place recursive relation <math>R</math> such that <math>x \in S \iff \exists t\ R(x,t)</math> || "Semi"-ness
|-
| The relation <math>x \in S</math> is <math>\Sigma_1</math> || "Semi"-ness
|-
| The relation <math>x\in S</math> has a computable partial verifying function, i.e., there exists a computable partial function <math>f</math> such that <math>x \in S \iff f(x) \simeq 1</math>.<ref>https://www.andrew.cmu.edu/user/kk3n/complearn/chapter6.pdf</ref> || "Semi"-ness
|}

User:IssaRice/Computability and logic/Characterization of recursively enumerable sets - Revision history

IssaRice at 08:54, 26 April 2019

IssaRice: IssaRice moved page User:IssaRice/Characterization of recursively enumerable sets to User:IssaRice/Computability and logic/Characterization of recursively enumerable sets

IssaRice at 04:40, 18 December 2018

IssaRice at 04:40, 18 December 2018

IssaRice at 04:36, 18 December 2018

IssaRice at 04:36, 18 December 2018

IssaRice at 04:33, 18 December 2018

IssaRice: Created page with "Let S be a set of natural numbers. The following are all equivalent. {| class="sortable wikitable" |- ! Property !! Emphasis |- | The elements of S..."

IssaRice: Created page with "Let $S$ be a set of natural numbers. The following are all equivalent. {| class="sortable wikitable" |- ! Property !! Emphasis |- | The elements of $S$ ..."