Course-of-values recursion - Revision history

82.25.27.218: /* References */

2024-04-01T16:05:11Z

References

← Previous revision		Revision as of 16:05, 1 April 2024
Line 68:		Line 68:

	* Hinman, P.G., 2006, ''Fundamentals of Mathematical Logic'', A K Peters.		* Hinman, P.G., 2006, ''Fundamentals of Mathematical Logic'', A K Peters.
	* Odifreddi, P.G., 1989, ''Classical Recursion Theory'', North Holland; second edition, 1999.		* [[Piergiorgio Odifreddi\|Odifreddi, P.G.]], 1989, ''Classical Recursion Theory'', North Holland; second edition, 1999.

	{{Mathematical logic}}		{{Mathematical logic}}

AksharVarma: #suggestededit-add 1.0

2023-06-09T10:50:55Z

#suggestededit-add 1.0

← Previous revision		Revision as of 10:50, 9 June 2023
Line 1:		Line 1:
			{{Short description\|Technique for defining number-theoretic functions by recursion}}
	{{No footnotes\|date=April 2009}}		{{No footnotes\|date=April 2009}}
	In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.		In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.

Mgkrupa: Added {{Mathematical logic}}

2022-08-06T22:41:21Z

Added {{Mathematical logic}}

← Previous revision		Revision as of 22:41, 6 August 2022
Line 64:		Line 64:
	Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'', ''A''(''m''+1, ''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).		Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'', ''A''(''m''+1, ''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).

	== References ==		==References==

	*Hinman, P.G., 2006, ''Fundamentals of Mathematical Logic'', A K Peters.
	*~~Odifreddi~~, P.G., ~~1989~~, ''~~Classical~~ ~~Recursion~~ ~~Theory~~'', ~~North~~ ~~Holland; second edition,~~ ~~1999~~.		* Hinman, P.G., 2006, ''Fundamentals of Mathematical Logic'', A K Peters.
			* Odifreddi, P.G., 1989, ''Classical Recursion Theory'', North Holland; second edition, 1999.

			{{Mathematical logic}}

	[[Category:Computability theory]]		[[Category:Computability theory]]

169.233.146.6: Undid revision 1044177671 by 169.233.146.6 (talk)

2021-09-13T23:57:52Z

Undid revision 1044177671 by 169.233.146.6 (talk)

← Previous revision		Revision as of 23:57, 13 September 2021
Line 7:		Line 7:
	The factorial function ''n''! is recursively defined by the rules		The factorial function ''n''! is recursively defined by the rules
	:<math>0! = 1,</math>		:<math>0! = 1,</math>
	:<math>(n+1)! = n(n+1).</math>		:<math>(n+1)! = n!(n+1).</math>
	This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations		This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations
	:<math>Fib(0) = 0,</math>		:<math>Fib(0) = 0,</math>

169.233.146.6 at 23:56, 13 September 2021

2021-09-13T23:56:43Z

← Previous revision		Revision as of 23:56, 13 September 2021
Line 7:		Line 7:
	The factorial function ''n''! is recursively defined by the rules		The factorial function ''n''! is recursively defined by the rules
	:<math>0! = 1,</math>		:<math>0! = 1,</math>
	:<math>(n+1)! = n!(n+1).</math>		:<math>(n+1)! = n(n+1).</math>
	This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations		This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations
	:<math>Fib(0) = 0,</math>		:<math>Fib(0) = 0,</math>

31.147.118.150: Everything below follows the convention of starting from zero (which is usual in computability). So this should be consistent.

2020-10-16T03:21:41Z

Everything below follows the convention of starting from zero (which is usual in computability). So this should be consistent.

← Previous revision		Revision as of 03:21, 16 October 2020
Line 1:		Line 1:
	{{No footnotes\|date=April 2009}}		{{No footnotes\|date=April 2009}}
	In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n''+1) is computed from the sequence <math>\langle f(1),f(2),\ldots,f(n)\rangle</math>.		In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.

	The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are [[primitive recursive]]. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a [[arity\|1-ary]] primitive recursive function ''g'' the value of ''g''(''n''+1) is computed only from ''g''(''n'') and ''n''.		The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are [[primitive recursive]]. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a [[arity\|1-ary]] primitive recursive function ''g'' the value of ''g''(''n''+1) is computed only from ''g''(''n'') and ''n''.

Dough34: /* Limitations */ add missing space

2019-01-15T18:30:35Z

Limitations: add missing space

← Previous revision		Revision as of 18:30, 15 January 2019
Line 62:		Line 62:
	Not every recursive definition can be transformed into a primitive recursive definition. One known example is [[Ackermann's function]], which is of the form ''A''(''m'',''n'') and is provably not primitive recursive.		Not every recursive definition can be transformed into a primitive recursive definition. One known example is [[Ackermann's function]], which is of the form ''A''(''m'',''n'') and is provably not primitive recursive.

	Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'',''A''(''m''+1,''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).		Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'', ''A''(''m''+1, ''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).

	== References ==		== References ==

Hayazin: /* Definition and examples */ Harmonized style

2018-05-06T19:14:57Z

Definition and examples: Harmonized style

← Previous revision		Revision as of 19:14, 6 May 2018
Line 6:		Line 6:
	==Definition and examples ==		==Definition and examples ==
	The factorial function ''n''! is recursively defined by the rules		The factorial function ''n''! is recursively defined by the rules
	:0! = 1,		:<math>0! = 1,</math>
	:(''n''+1)! = (''n''+1~~)*(''n''!~~).		:<math>(n+1)! = n!(n+1).</math>
	This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations		This recursion is a '''primitive recursion''' because it computes the next value (''n''+1)! of the function based on the value of ''n'' and the previous value ''n''! of the function. On the other hand, the function Fib(''n''), which returns the ''n''th [[Fibonacci number]], is defined with the recursion equations
	:Fib(0) = 0,		:<math>Fib(0) = 0,</math>
	:Fib(1) = 1,		:<math>Fib(1) = 1,</math>
	:Fib(''n''+2) = Fib(''n''+1) + Fib(''n'').		:<math>Fib(n+2) = Fib(n+1) + Fib(n).</math>
	In order to compute Fib(''n''+2), the last ''two'' values of the Fib function are required. Finally, consider the function ''g'' defined with the recursion equations		In order to compute Fib(''n''+2), the last ''two'' values of the Fib function are required. Finally, consider the function ''g'' defined with the recursion equations
	:g(0) = 0,		:<math>g(0) = 0,</math>
	:<math>g(n+1) = \sum_{i = 0}^{n} g(i)^{n-i}</math>.		:<math>g(n+1) = \sum_{i = 0}^{n} g(i)^{n-i}.</math>
	To compute ''g''(''n''+1) using these equations, all the previous values of ''g'' must be computed; no fixed finite number of previous values is sufficient in general for the computation of ''g''. The functions Fib and ''g'' are examples of functions defined by course-of-values recursion.		To compute ''g''(''n''+1) using these equations, all the previous values of ''g'' must be computed; no fixed finite number of previous values is sufficient in general for the computation of ''g''. The functions Fib and ''g'' are examples of functions defined by course-of-values recursion.

Line 21:		Line 21:
	where <math>\langle f(0), f(1), \ldots, f(n-1)\rangle</math> is a [[Gödel_numbering_for_sequences\|Gödel number]] encoding the indicated sequence.		where <math>\langle f(0), f(1), \ldots, f(n-1)\rangle</math> is a [[Gödel_numbering_for_sequences\|Gödel number]] encoding the indicated sequence.
	In particular		In particular
	:<math>f(0) = h(0,\langle\rangle),</math>		:<math>f(0) = h(0,\langle\rangle)</math>
	provides the initial value of the recursion. The function ''h'' might test its first argument to provide explicit initial values, for instance for Fib one could use the function defined by		provides the initial value of the recursion. The function ''h'' might test its first argument to provide explicit initial values, for instance for Fib one could use the function defined by
	:<math>h(n,s)=\begin{cases}n&\text{if }n<2\\ s[n-2]+s[n-1]&\text{if }n\geq2\end{cases}</math>		:<math>h(n,s)=\begin{cases}n&\text{if }n<2\\ s[n-2]+s[n-1]&\text{if }n\geq2\end{cases}</math>

2001:984:9396:1:F521:E689:E2C5:27DE: fixed typo

2017-05-10T06:58:30Z

fixed typo

← Previous revision		Revision as of 06:58, 10 May 2017
Line 60:		Line 60:

	== Limitations ==		== Limitations ==
	Not every recursive definition can be transformed into a primitive recursive definition. One known example is [[Ackermann's function]], which is of the form ''A''(''m'',''n'') and is provably not primitive ~~resursive~~.		Not every recursive definition can be transformed into a primitive recursive definition. One known example is [[Ackermann's function]], which is of the form ''A''(''m'',''n'') and is provably not primitive recursive.

	Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'',''A''(''m''+1,''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).		Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'',''A''(''m''+1,''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).

Dan Gluck: Limitations

2016-06-18T09:54:14Z

Limitations

← Previous revision		Revision as of 09:54, 18 June 2016
Line 58:		Line 58:
	:<math>\prod_{i = 0}^k p_i^{(n_i +1)}</math>,		:<math>\prod_{i = 0}^k p_i^{(n_i +1)}</math>,
	which makes it possible to distinguish the codes for the sequences <math>\langle 0 \rangle</math> and <math>\langle 0,0\rangle</math>.		which makes it possible to distinguish the codes for the sequences <math>\langle 0 \rangle</math> and <math>\langle 0,0\rangle</math>.

			== Limitations ==
			Not every recursive definition can be transformed into a primitive recursive definition. One known example is [[Ackermann's function]], which is of the form ''A''(''m'',''n'') and is provably not primitive resursive.

			Indeed, every new value ''A''(''m''+1, ''n'') depends on the sequence of previously defined values ''A''(''i'', ''j''), but the ''i''-s and ''j''-s for which values should be included in this sequence depend themselves on previously computed values of the function; namely (''i'', ''j'') = (''m'',''A''(''m''+1,''n'')). Thus one cannot encode the previously computed sequence of values in a primitive recursive way in the manner suggested above (or at all, as it turns out this function is not primitive recursive).

	== References ==		== References ==

← Previous revision		Revision as of 10:50, 9 June 2023
Line 1:		Line 1:
			{{Short description\|Technique for defining number-theoretic functions by recursion}}
	{{No footnotes\|date=April 2009}}		{{No footnotes\|date=April 2009}}
	In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.		In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.

← Previous revision		Revision as of 03:21, 16 October 2020
Line 1:		Line 1:
	{{No footnotes\|date=April 2009}}		{{No footnotes\|date=April 2009}}
	In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n''+1) is computed from the sequence <math>\langle f(1),f(2),\ldots,f(n)\rangle</math>.		In [[computability theory]], '''course-of-values recursion''' is a technique for defining [[number-theoretic function]]s by [[Recursion (computer science)\|recursion]]. In a definition of a function ''f'' by course-of-values recursion, the value of ''f''(''n'') is computed from the sequence <math>\langle f(0),f(1),\ldots,f(n-1)\rangle</math>.

	The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are [[primitive recursive]]. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a [[arity\|1-ary]] primitive recursive function ''g'' the value of ''g''(''n''+1) is computed only from ''g''(''n'') and ''n''.		The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are [[primitive recursive]]. Contrary to course-of-values recursion, in primitive recursion the computation of a value of a function requires only the previous value; for example, for a [[arity\|1-ary]] primitive recursive function ''g'' the value of ''g''(''n''+1) is computed only from ''g''(''n'') and ''n''.