User:IssaRice/Computability and logic/Bounded computation trick - Revision history

IssaRice at 23:01, 24 March 2019

2019-03-24T23:01:43Z

← Older revision		Revision as of 23:01, 24 March 2019
Line 8:		Line 8:
	* Peter Smith's proof that domain of an algorithm implies effectively enumerable (theorem 3.5)		* Peter Smith's proof that domain of an algorithm implies effectively enumerable (theorem 3.5)
	* Peter Smith's proof that K is recursively enumerable (theorem 3.8)		* Peter Smith's proof that K is recursively enumerable (theorem 3.8)
	* the ~~second~~ graph principle		* the first graph principle
	* goedel's beta function (this one is slightly different, i think)		* goedel's beta function (this one is slightly different, i think)
	* definition of Prf(m,n) in logic		* definition of Prf(m,n) in logic
	* when arithmetizing syntax in logic (see e.g. Leary and Kristiansen), there's the need to find bounds for things to ensure the predicates are primitive recursive		* when arithmetizing syntax in logic (see e.g. Leary and Kristiansen), there's the need to find bounds for things to ensure the predicates are primitive recursive

IssaRice at 22:51, 24 March 2019

2019-03-24T22:51:51Z

← Older revision		Revision as of 22:51, 24 March 2019
Line 3:		Line 3:
	Some examples of this trick in use:		Some examples of this trick in use:

			* the idea of dovetailing
	* showing that a recursively enumerable set is primitive-recursively enumerable		* showing that a recursively enumerable set is primitive-recursively enumerable
	* Kleene's T predicate and normal form		* Kleene's T predicate and normal form

IssaRice at 22:30, 24 March 2019

2019-03-24T22:30:26Z

← Older revision		Revision as of 22:30, 24 March 2019
Line 10:		Line 10:
	* goedel's beta function (this one is slightly different, i think)		* goedel's beta function (this one is slightly different, i think)
	* definition of Prf(m,n) in logic		* definition of Prf(m,n) in logic
			* when arithmetizing syntax in logic (see e.g. Leary and Kristiansen), there's the need to find bounds for things to ensure the predicates are primitive recursive

IssaRice at 22:29, 24 March 2019

2019-03-24T22:29:01Z

← Older revision		Revision as of 22:29, 24 March 2019
Line 9:		Line 9:
	* the second graph principle		* the second graph principle
	* goedel's beta function (this one is slightly different, i think)		* goedel's beta function (this one is slightly different, i think)
			* definition of Prf(m,n) in logic

IssaRice at 22:28, 24 March 2019

2019-03-24T22:28:02Z

← Older revision		Revision as of 22:28, 24 March 2019
Line 8:		Line 8:
	* Peter Smith's proof that K is recursively enumerable (theorem 3.8)		* Peter Smith's proof that K is recursively enumerable (theorem 3.8)
	* the second graph principle		* the second graph principle
	* goedel's beta function		* goedel's beta function (this one is slightly different, i think)

IssaRice at 22:24, 24 March 2019

2019-03-24T22:24:06Z

← Older revision		Revision as of 22:24, 24 March 2019
Line 8:		Line 8:
	* Peter Smith's proof that K is recursively enumerable (theorem 3.8)		* Peter Smith's proof that K is recursively enumerable (theorem 3.8)
	* the second graph principle		* the second graph principle
			* goedel's beta function

IssaRice at 22:21, 24 March 2019

2019-03-24T22:21:47Z

← Older revision		Revision as of 22:21, 24 March 2019
Line 5:		Line 5:
	* showing that a recursively enumerable set is primitive-recursively enumerable		* showing that a recursively enumerable set is primitive-recursively enumerable
	* Kleene's T predicate and normal form		* Kleene's T predicate and normal form
	* Peter Smith's proof that		* Peter Smith's proof that domain of an algorithm implies effectively enumerable (theorem 3.5)
			* Peter Smith's proof that K is recursively enumerable (theorem 3.8)
	* the second graph principle		* the second graph principle

IssaRice: Created page with "Instead of saying "compute this thing" you can say "compute this thing for $n$ steps", then let $n$ vary. This trick makes the computation bounded, which..."

2019-03-24T22:08:54Z

Created page with "Instead of saying "compute this thing" you can say "compute this thing for <math>n</math> steps", then let <math>n</math> vary. This trick makes the computation bounded, which..."

New page

Instead of saying "compute this thing" you can say "compute this thing for <math>n</math> steps", then let <math>n</math> vary. This trick makes the computation bounded, which is useful in certain situations.

Some examples of this trick in use:

* showing that a recursively enumerable set is primitive-recursively enumerable
* Kleene's T predicate and normal form
* Peter Smith's proof that
* the second graph principle