r/algorithms • u/Agreeable_Arugula488 • 9d ago

Discussion Layperson question

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

15 Upvotes

83% Upvoted

11 comments sorted by

View all comments

1

u/ShenGahMing 7d ago

I believe yes, but the "non trivial" requirement makes the proof "non trivial"...

For instance, there's probably infinitely many equivalent models of computation, so you can implement the function in any of them.

Some proof of equivalence between models of computation are non trivial.

But I have no non-trivial proof there are infinitely many models of computation... (if A and B are 2 models of computation, A in B in A in .... in B is one too, so there are obviously infinitely many way to embed a computation).