# For any sequence, is there a function that gives another sequence? **URL:** \ **Category:** Factual Questions\ **Created:** [October 29, 2006, 10:22am UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317 "2006-10-29T10:22:01Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![yelimS](https://avatars.discourse-cdn.com/v4/letter/y/54ee81/32.png) [@yelimS](https://boards.straightdope.com/u/yelimS)\ **Post date:** [October 29, 2006, 10:22am UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/1 "2006-10-29T10:22:01Z")
Well, just that really. I suppose irrational numbers are asking a bit too much, but what other limitations might there be? ---
**Author:** ![yelimS](https://avatars.discourse-cdn.com/v4/letter/y/54ee81/32.png) [@yelimS](https://boards.straightdope.com/u/yelimS)\ **Post date:** [October 29, 2006, 10:23am UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/2 "2006-10-29T10:23:52Z")
Specific! Specific sequences, of course! Like, find a function that transforms 1, 2, -1099481 and 15 into 3, -2943784, 29393 and -11. ---
**Author:** ![Napier](https://avatars.discourse-cdn.com/v4/letter/n/ce73a5/32.png) [@Napier](https://boards.straightdope.com/u/Napier)\ **Post date:** [October 29, 2006, 12:37pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/3 "2006-10-29T12:37:18Z")
For any given finite sequence there is an infinite number of functions that return any other given sequence. But I bet there are given infinite sequences such that no other function returns them. For example, a random number generator that (unlike most commercial ones) does not use a purely mathematical algorithm. If you connect a source of noise, like an amplified resistor, to an analog to digital converter, I think you generate an arbitrarily long sequence that can’t be generated by any function from a given sequence. ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [October 29, 2006, 2:32pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/4 "2006-10-29T14:32:50Z")
> [@Napier](#): > > But I bet there are given infinite sequences such that no other function returns them. Not according to the standard definition of a sequence. A sequence of real numbers _x_[sub]1[/sub], _x_[sub]2[/sub], _x_[sub]3[/sub], . . . is, by definition, a real-valued function on the numbers 1, 2, 3, . . .. Therefore, if you are given an infinite sequence, then you are given a function that returns that sequence. I’m not sure just what the OP is asking, though. Can you give an example what you mean by a function giving another sequence? If the question is “Given sequences _x_[sub]1[/sub], _x_[sub]2[/sub], _x_[sub]3[/sub], . . . and _y_[sub]1[/sub], _y_[sub]2[/sub], _y_[sub]3[/sub], . . ., is there always a function _f_ such that _f_(_x_[sub]1[/sub]) = _y_[sub]1[/sub], _f_(_x_[sub]2[/sub]) = _y_[sub]2[/sub], _f_(_x_[sub]3[/sub]) = _y_[sub]3[/sub], . . . ?”, then the answer is “No.” Let the first sequence be 1, 1, 1, . . ., and let the second sequence 1, 2, 3, . . .. Then such a function _f_ would have to map 1 to 1, and 1 to 2, and 1 to 3, etc. But a function can only map 1 to one of these values, so this is impossible. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 29, 2006, 3:15pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/5 "2006-10-29T15:15:00Z")
Such a function exists if your sequence x[sub]1[/sub], x[sub]2[/sub], x[sub]3[/sub], … has the property that x[sub]i[/sub] = x[sub]j[/sub] implies that i = j. I’m not sure what you’d call that, or that it’s even a particularly interesting property. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [October 29, 2006, 5:37pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/6 "2006-10-29T17:37:41Z")
[QUOTE=ultrafilter] Such a function exists if your sequence x[sub]1[/sub], x[sub]2[/sub], x[sub]3[/sub], … has the property that x[sub]i[/sub] = x[sub]j[/sub] implies that i = j. I’m not sure what you’d call that, or that it’s even a particularly interesting property. [/QUOTE] If you define a sequence as **Tyrell McAlister** said, I’d call this a **one-to-one** real-valued function on the natural numbers. Or just “a sequence in which no term appears more than once.” Given the definition of a function as “a set of ordered pairs, no two of which have the same first element,” then, as the previous two posts explain, any time you have two sequences (either both infinite, or both finite of the same length), you automatically have a function that maps the first to the second **iff** the first sequence has no repeated terms. If, for a “function,” you’re thinking of a continuous function, or a function that can be defined by some algebraic formula, I’m not sure what the conditions would have to be. If both sequences were finite and had only two terms, you could find a linear function; if they had three terms, you could usually (but not always) find a quadratic function. For any two finite seuqences, I suppose you could have a piecewise linear function (imagine plotting all the points (x[sub]i[/sub], y[sub]i[/sub]) and connecting the dots). ---
**Author:** ![yelimS](https://avatars.discourse-cdn.com/v4/letter/y/54ee81/32.png) [@yelimS](https://boards.straightdope.com/u/yelimS)\ **Post date:** [October 29, 2006, 9:19pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/7 "2006-10-29T21:19:36Z")
Missed some bits there, I see. Of course, any number in sequence x would always be returned as the same number in sequence y, so that if x1 = x100 then y1 = y100 (How do you make those small numbers?). Also, the reason I’m asking is because I’m reading about artificial intelligence and was curious about the limits of evolutionary programming. If there is a function that connects any two sets of numbers (given that all in the first set are unique, of course), then it appears that all you would need for an “intelligence function” is working out what kind of parameters it required and their relative values. Or so it seems. Any ideas? ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [October 29, 2006, 10:14pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/8 "2006-10-29T22:14:16Z")
Not sure how to address your larger question, **yelimS** , but you make subscripts by typing x[sub]1[/sub] to get x[sub]1[/sub]. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [October 29, 2006, 11:33pm UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/9 "2006-10-29T23:33:53Z")
[QUOTE=yelimS] Missed some bits there, I see. Of course, any number in sequence x would always be returned as the same number in sequence y, so that if x1 = x100 then y1 = y100 (How do you make those small numbers?). [/QUOTE] In that case, there is always a function, and it’s definable so long as both sequences are definable. Let \ and \ be two such sequences. Then the function that maps x(k) to y(k) is given by f(n) = y([symbol]m[/symbol]k(x(k) = n)), where [symbol]m[/symbol] is the unrestricted [symbol]m[/symbol]-operator. There’s a detailed definition in [this book](http://www.amazon.com/Introduction-Mathematical-Fourth-Elliott-Mendelson/dp/0412808307/sr=8-1/qid=1162164399/ref=pd_bbs_sr_1/102-0266053-3017760?ie=UTF8&s=books), but the short version is that [symbol]m[/symbol]k(x(k) = n) denotes the least k such that x(k) = n if there is one. The implication here is that even if x(k) and y(k) can be quickly calculated by computer programs that will always terminate, the program to calculate f may run forever for some inputs. If you’re lucky enough that x(k) is one-to-one, you can use f(n) = y(x[sup]-1/sup), and that’s guaranteed to have the same computability properties as y and x. That’s the special case that I mentioned earlier. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [October 30, 2006, 7:38am UTC](https://boards.straightdope.com/t/for-any-sequence-is-there-a-function-that-gives-another-sequence/378317/10 "2006-10-30T07:38:55Z")
[QUOTE=Tyrrell McAllister] Not according to the standard definition of a sequence. A sequence of real numbers _x_[sub]1[/sub], _x_[sub]2[/sub], _x_[sub]3[/sub], . . . is, by definition, a real-valued function on the numbers 1, 2, 3, . . .. Therefore, if you are given an infinite sequence, then you are given a function that returns that sequence. I’m not sure just what the OP is asking, though. Can you give an example what you mean by a function giving another sequence? If the question is “Given sequences _x_[sub]1[/sub], _x_[sub]2[/sub], _x_[sub]3[/sub], . . . and _y_[sub]1[/sub], _y_[sub]2[/sub], _y_[sub]3[/sub], . . ., is there always a function _f_ such that _f_(_x_[sub]1[/sub]) = _y_[sub]1[/sub], _f_(_x_[sub]2[/sub]) = _y_[sub]2[/sub], _f_(_x_[sub]3[/sub]) = _y_[sub]3[/sub], . . . ?”, then the answer is “No.” Let the first sequence be 1, 1, 1, . . ., and let the second sequence 1, 2, 3, . . .. Then such a function _f_ would have to map 1 to 1, and 1 to 2, and 1 to 3, etc. But a function can only map 1 to one of these values, so this is impossible. [/QUOTE] Sure, but there will be a function _f_(_x_[sub]i[/sub], _i_) = _y_[sub]i[/sub]