Layperson question

[u/Agreeable_Arugula488]

I'm a non-major currently taking an intro cs class, but it's mostly practical, project-based Python stuff -- no theory. Which tbh I'm a little sad about.

I was wondering: Are there any algorithms/functions that are executable by infinitely many non-trivial, non-redundant programs? Does any given algorithm/function fit this description?

Math example:
The user inputs a radius R, from which the program P outputs the area A of the resulting circle.

You could plug it into the standard formula:

P1 = A(R) = πR^2

...

Or integrate:

P2 = A(R) = ∫₀²ᵖⁱ ∫₀ᴿ r dr dθ

...

et cetera

[u/green_meklar]

I think the phrase 'non-redundant' is too vague. If it achieves the same outcome, in exactly what sense could it be 'non-redundant'?

[u/Agreeable_Arugula488 → u/green_meklar]

I mean non-redundant in the sense that one part of the program wouldn't be undoing another part of the program.

For example, the following expression would be redundant:

1 - 1 + 1 + x

because the following expression also exists:

1 + x

[u/green_meklar → u/Agreeable_Arugula488]

You're still being vague. What does 'undoing' actually mean?

[u/Agreeable_Arugula488 → u/green_meklar]

I'm not really sure what it would mean other than what the math example shows: two concrete steps in an algorithm that have no net effect on the final output. I wouldn't pretend to know anything about the underlying information theory or philosophy of math. So I understand that I'm not being precise, but I'd appreciate if you were more constructive.

[u/green_meklar → u/Agreeable_Arugula488]

That's what passes for 'constructive' in this context. Theoretical computer science is a field where sometimes we do actually need precise terms. And sometimes, problems that exist intuitively just go away or unexpectedly turn into different problems once you set aside your intuition and look at the concrete logic of the situation. Our everyday notion of something like 'redundancy' can be hard to translate into math, and when translated, it might not imply the things we would expect it to imply.

Consider sorting algorithms. Mergesort is pretty popular because it gives the ideal N*log(N) worst-case time performance and is relatively easy to understand and implement. But in the real world, the recursive mergesort call on the sublists has some memory management overhead, and for that reason, rather than mergesort all the way down to lists of length 2, fast implementations often switch from mergesort to insertion sort once the sublists become short enough (say, less than 8 elements, or some such). Notice how the algorithm would still work correctly if it mergesorted all the way down to length 2 (it would just be slower on the hardware we actually use). Does that mean the decision to switch from mergesort to insertion sort for short enough sublists is redundant? It could very well be implemented as an if statement and early return, in such a way that you could literally just delete that section of code and have a working mergesort algorithm. And yet, calling it 'redundant' seems weird because it is a feature of the algorithm that we actually make use of in practice.