next up previous
Next: Decidability of the uniqueness Up: MPR-online 1998Vol.3, No.1 Previous: A special type of

Analysis of the uniqueness problem for the special type of number sequence task

In this section, we will show that both hypotheses formulated at the end of Section 5 are false. The following proposition disproves Hypothesis 5.4 I.

6.1 Proposition. Each tex2html_wrap_inline2479-recursive number sequence tex2html_wrap_inline2347 with tex2html_wrap_inline2483 is additionally

tex2html_wrap_inline2485-recursive for appropriate tex2html_wrap_inline2487;
tex2html_wrap_inline2489-recursive for appropriate tex2html_wrap_inline2491;
tex2html_wrap_inline2493-recursive for appropriate tex2html_wrap_inline2495 in the case that tex2html_wrap_inline2497;
tex2html_wrap_inline2499-recursive for appropriate tex2html_wrap_inline2501;
tex2html_wrap_inline2503-recursive for appropriate tex2html_wrap_inline2505.

PROOF. Let tex2html_wrap_inline2347 be some tex2html_wrap_inline2479-recursive sequence with tex2html_wrap_inline2511.

For tex2html_wrap_inline2513 holds:
with tex2html_wrap_inline2515 for tex2html_wrap_inline2517.

For tex2html_wrap_inline2519 holds:
with tex2html_wrap_inline2521 for tex2html_wrap_inline2517.
(Note that the case tex2html_wrap_inline2525 need not be excluded!)

For tex2html_wrap_inline2513 holds:
with tex2html_wrap_inline2529 since tex2html_wrap_inline2531.

For tex2html_wrap_inline2519 using (c) we get
with tex2html_wrap_inline2535 since tex2html_wrap_inline2537; the condition tex2html_wrap_inline2497 needed in (c) can be abandoned.

For tex2html_wrap_inline2519 we get using (c)
with tex2html_wrap_inline2543 since tex2html_wrap_inline2517 (again the condition tex2html_wrap_inline2497 can be abandoned). tex2html_wrap_inline2011

To summarize, Proposition 6.1 tells us that each sequence of natural numbers that can be represented by a recursion formula from domain tex2html_wrap_inline2551 is additionally representable by recursion formulae from the domains tex2html_wrap_inline2553 and tex2html_wrap_inline2309. This result for the task-type analyzed here corresponds to the result stated in Theorem 4.9. In spite of the strong Restriction (R) for permitted recursion formulae, for each natural number sequence there exist permissible recursion formulae of higher degrees whenever a permissible recursion formula of degree r=1 exists. Observe that this statement (as the proof to Proposition 6.1 reveals) holds for each arbitrary linear-recursive number sequence under (R) of at least four members. Thus, the uncovered non-uniqueness of solution does not depend on the length of the given sequence and thus cannot be prevented by prolonging the given sequence.

There also exist classes of number sequences of the form tex2html_wrap_inline2347 which are recursive of degree 2 but not of degree 1, and that can be described by recursion formulae of degree 3. This is demonstrated by the following examples.

6.2 Examples.

Each tex2html_wrap_inline2561-recursive number sequence tex2html_wrap_inline2347 is for each tex2html_wrap_inline2565 additionally tex2html_wrap_inline2567-recursive with tex2html_wrap_inline2569:
Numerical example: tex2html_wrap_inline2571 (c=1).

Each tex2html_wrap_inline2575-recursive number sequence tex2html_wrap_inline2347 is for each tex2html_wrap_inline2565 additionally tex2html_wrap_inline2581-recursive with tex2html_wrap_inline2583:
Numerical example: tex2html_wrap_inline2585 (c=11).

Each tex2html_wrap_inline2575-recursive number sequence tex2html_wrap_inline2347 is for each tex2html_wrap_inline2565 additionally tex2html_wrap_inline2595-recursive with tex2html_wrap_inline2597:
Numerical example: tex2html_wrap_inline2599 (c=3).

Note here that none of the sequences in the three examples is linear-recursive of degree 1 as required.

By the preceding Proposition 6.1 and the examples of 6.2 the Hypothesis 5.4 I. is unequivocally disproved. Admittedly, the formulae derived in the proof of 6.1 all lead to equal extensions of the given number sequence. That, of course, even this type of non-uniqueness may cause serious problems in various applications has been emphasized in connection with the uniqueness problem explicated in 3.3.

The cases we have been dealing with up until now might at least point to the correctness of Hypothesis 5.4 II. This hypothesis includes that, at least under the strong Restriction (R), alternative recursion formulae (should they exist for some sequence) all lead to identic extensions. Unfortunately, also this part of Hypothesis 5.4 proves to be false. The following proposition describes classes of number sequences that disprove this hypothesis.

6.3 Proposition. Let tex2html_wrap_inline2347 be a non-constant number sequence, and let tex2html_wrap_inline2605, with tex2html_wrap_inline2607 for tex2html_wrap_inline2609 be the sequence of differences of each two subsequent members of tex2html_wrap_inline2303. Then the following hold:

For tex2html_wrap_inline2613, the sequence tex2html_wrap_inline2303 is tex2html_wrap_inline2617-recursive with tex2html_wrap_inline2619 arbitrary, tex2html_wrap_inline2621, and with the tex2html_wrap_inline2617-extension tex2html_wrap_inline2363 with tex2html_wrap_inline2627 for each tex2html_wrap_inline2629.

For tex2html_wrap_inline2631, the sequence tex2html_wrap_inline2303 is tex2html_wrap_inline2635-recursive with tex2html_wrap_inline2041 arbitrary, tex2html_wrap_inline2639, and with the tex2html_wrap_inline2635-extension tex2html_wrap_inline2363 with tex2html_wrap_inline2645 for each tex2html_wrap_inline2647.

For tex2html_wrap_inline2649, the sequence tex2html_wrap_inline2303 is tex2html_wrap_inline2653-recursive with tex2html_wrap_inline2655 arbitrary, tex2html_wrap_inline2657, and with the tex2html_wrap_inline2653-extension tex2html_wrap_inline2363 with tex2html_wrap_inline2663 for each tex2html_wrap_inline2665.

In each of the three cases holds: The member tex2html_wrap_inline2667 is essentially dependent on the occurring parameter since the sequence tex2html_wrap_inline2303 is non-constant.

PROOF. For n=6 from (6) we obtain the matrix

(a) For tex2html_wrap_inline2613, we obtain from (7) the matrix
where tex2html_wrap_inline2675 since the sequence is non-constant. The corresponding LES in D has the solutions tex2html_wrap_inline2679 with tex2html_wrap_inline2619 arbitrary, and
For tex2html_wrap_inline2667 we obtain
hereby tex2html_wrap_inline2667 would be independent of tex2html_wrap_inline2687 if and only if tex2html_wrap_inline2689 which is not the case since the sequence is non-constant.

(b) For tex2html_wrap_inline2631, the matrix (7) transforms to
where tex2html_wrap_inline2675 since the sequence is non-constant. Thus, solutions of the corresponding LES in D are formulae of type tex2html_wrap_inline2697 with tex2html_wrap_inline2041 arbitrary, and
For tex2html_wrap_inline2667 we obtain
where tex2html_wrap_inline2667 is essentially dependent of tex2html_wrap_inline2053 because tex2html_wrap_inline2707 since the sequence is non-constant.

(c) For tex2html_wrap_inline2649, we obtain from (7) the matrix
where tex2html_wrap_inline2711 since the sequence is non-constant. Solutions of the corresponding LES in D are formulae of type tex2html_wrap_inline2715 with tex2html_wrap_inline2655 arbitrary, and
For tex2html_wrap_inline2667 we obtain
where tex2html_wrap_inline2667 is not independent of tex2html_wrap_inline2055 since tex2html_wrap_inline2711. tex2html_wrap_inline2011

Remark. One easily shows that, in the case of our particular type of number sequence tasks, exactly the previously described classes of (non-constant) sequences have the demonstrated problematic property of multiple representability and extensionability.

6.4 Examples.

The sequence tex2html_wrap_inline2729 is tex2html_wrap_inline2617-recursive with tex2html_wrap_inline2619 arbitrary, tex2html_wrap_inline2735 and tex2html_wrap_inline2737. For instance, this sequence is for
tex2html_wrap_inline2739: tex2html_wrap_inline2741-recursive with tex2html_wrap_inline2743;
tex2html_wrap_inline2745: tex2html_wrap_inline2747-recursive with tex2html_wrap_inline2749;
tex2html_wrap_inline2751: tex2html_wrap_inline2753-recursive with tex2html_wrap_inline2755.

The sequence tex2html_wrap_inline2757 is tex2html_wrap_inline2635-recursive with tex2html_wrap_inline2041 arbitrary, tex2html_wrap_inline2763 and tex2html_wrap_inline2765. For instance, this sequence is for
tex2html_wrap_inline2767: tex2html_wrap_inline2769-recursive with tex2html_wrap_inline2771;
tex2html_wrap_inline2773: tex2html_wrap_inline2775-recursive with tex2html_wrap_inline2777;
tex2html_wrap_inline2779: tex2html_wrap_inline2781-recursive with tex2html_wrap_inline2783.

The sequence tex2html_wrap_inline2785 is tex2html_wrap_inline2653-recursive with tex2html_wrap_inline2655 arbitrary, tex2html_wrap_inline2791 and tex2html_wrap_inline2793. For instance, this sequence is for
tex2html_wrap_inline2795: tex2html_wrap_inline2797-recursive with tex2html_wrap_inline2771;
tex2html_wrap_inline2801: tex2html_wrap_inline2803-recursive with tex2html_wrap_inline2805.

To summarize, Proposition 6.3 reveals that certain classes of number sequences can be characterized by infinitely many recursion formulae of the same type where each formula generates a different extension of the sequence. This result clearly disproves Hypothesis 5.4 II. Moreover, particularly the examples in 6.4 should illustrate that alternative solutions to a number sequence task need not differ considerably in their complexity, whereas they produce differing extensions of the given sequence. To make matters worse, observe that each sequence-type described in 6.4 is not representable by any recursion formula of some lower degree; thus, no formulae exist that can be deemed the ''simplest'' in a psychological sense.

After both hypotheses connected to the Restriction (R) have been proven false, the justified question remains:

Do 6-term sequences of natural numbers, that under the Restriction (R) can be represented uniquely through some recursion formula from D (and thus also have unique extensions), exist at all ?
If the answer is yes: How can these sequences be characterized ?
This question can be easily answered on the basis of the results from Section 4.

next up previous
Next: Decidability of the uniqueness Up: MPR-online 1998Vol.3, No.1 Previous: A special type of

Methods of Psychological Research 1998 Vol.3 No.1
© 1998 Pabst Science Publishers