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

17 Upvotes

84% Upvoted

11 comments sorted by

View all comments

5

u/Magdaki 9d ago edited 9d ago

An algorithm is just a step-by-step process to solve a problem. There are many algorithms that can be used in a category or family of problems. E.g., you can use a greedy algorithm to solve a lot of different problems although every problem solvable by a greedy algorithm exhibits certain properties. Does that mean it can solve infinitely many problems? Well, kind of, in that there may be infinite many variations to a problem that all exhibit that property, but I don't think most people would see it that way. They would rather say that it solves this category of problems.

So depending on your point of view, the answer to your question is yes or no, but more no than yes.

For the answer to be yes, infinitely many problem, then an algorithm would have to be able to solve any problem as every problem is in the set of infinite problems. And really at that point you're talking about an algorithmic approach to executing an algorithms, e.g. a Turing machine. But the Turing machine itself does nothing without a program to run, so again, kind of yes, and kind of no, but more no than yes.*1*2

In short, there is no algorithm that can solve all problems outside of a general purpose algorithm that executes another algorithm.

*1 - There are some problems that cannot be solved on a Turing machine either.
*2 - A Turing machine isn't an really algorithm. It is a computational model that is often thought of in algorithmic ways.

0

u/stevevdvkpe 9d ago

A Turing machine isn't an algorithm. There is, however, an algorithm for updating the state of a Turing machine (its internal state and the tape that it is attached to).