20
Every algorithm must always finish after a finite number of steps?
It seems trivial but I ask because it generated another doubt that can be exposed in the following example:
enquanto (VERDADE){
ouvir_ligações_porta_8080
}
The previous example is an algorithm or not?
14
This is an algorithm, of course. And the algorithm doesn’t necessarily have to be finite. It’s desirable, but not mandatory. When this occurs it is called a computational method, as stated in the book The Art of Computer Programming, where one of the characteristics of the algorithm is finitude is defined. There is an exception to this case as there are situations where only an intervention outside the algorithm is expected to end it. This case is called reactive process (also taken from the same book).
According to the comments we conclude that the most correct term is that it is a computational method and not an algorithm. At least formally speaking. Not that anyone will have the wrong understanding of calling it an algorithm. It seems that academically, the branch of computing considers as an essential condition to call something an algorithm, among other characteristics, that it is finite.
If you want to use the terms academically, it’s better to say you have a computational method there. If you want to express something that everyone understands, you can call it an algorithm at will, no one will fight with you, everyone will understand and this is what matters.
Ok, but the author of the same book says that an algorithm should (the term even used is "must"), so the idea is to try to figure out if it should and why it should not and the other way around with the proper whys.
Read what is between parentheses in the same book item. This "must" is to suit this feature, not to be an algorithm.
I’m beginning to see it’s really a matter of interpretation. I don’t get/get the same idea, and looking at this sentence "A PROCEDURE that as all of the characteritics of an Algorithm except taht it possibly Lacks on finiteness MAY BE CALLED a COMPUTATIONAL METHOD", that is, I understand that procedures like my example is a computational method and not necessarily an algorithm.
That may be so. But is the doubt, algorithm and computational method are antagonistic or the second is a type of the first? Not that I think it has much practical relevance. But it’s an interesting curiosity.
I wouldn’t say antagonistic, but the hereditary relationship between them I don’t know. It seems to me that an algorithm can be a computational method any more than all computational methods are algorithms. And on the other hand, I may have algorithms that are not necessarily translated into computational methods.
12
The best consideration to make is that your example is a computational method, but not an algorithm. I will argue why this statement follows.
Like:
Let’s consider that the meaning of the word algorithm is the same as the equivalent in English Algorithm. So we can look for the definition of reliable and weighty sources in math and computing media.
Definition by Cambrige Dictionary:
A set of Mathematical Instructions that must be Followed in a Fixed order, and that, especially if Given to a computer, will help to calculate an Answer to a Mathematical problem.
Set of mathematical instructions that must be followed in a fixed order, and which, especially if given to a computer, will help calculate an answer to a mathematical problem.
Definition by the Oxford Dictionary:
Math. and Computing. A Procedure or set of Rules used in calculation and problem-solving. A precisely defined set of Mathematical or Logical Operations for the performance of a particular task.
Mathematics. and Computation. A procedure or set of rules used in the calculation and resolution of problems. A well-defined set of mathematical or logical operations for performing a given task.
Definition in Wolfram Mathworld:
An Algorithm is a specific set of Instructions for Carrying out a Procedure or solving a problem, usually with the requirement that the Procedure terminate at some point.
An algorithm is a specific set of instructions for performing a procedure or to solve a problem, usually with the requirement that the procedure ends at some point.
None of the three definitions explicitly rigorously states that an algorithm must terminate.
The classical definition of an algorithm is that of a sequential procedure ending at some point. However, new types of algorithms have emerged, such as parallel, interactive, distributed, analog, and quantum algorithms, which do not fit the classical definition. Thus, the concept of algorithm is still in the process of development and is not strictly defined.
But in practice, hardly a program that does not end will be said as an algorithm. An algorithm must solve a problem and therefore usually return a value that represents the solution. If at some point the solution has already been calculated, why should the algorithm continue? And if the solution is never calculated, the algorithm has no practical sense. The concept of an algorithm that does not end is more for theoretical than practical questions.
Therefore ouvir_ligações_porta_8080 is an algorithm because it solves a problem.
Already enquanto(VERDADE) is a computational method that calls an algorithm several times, but it never gives a final answer to its problem, so it would be better not to call it an algorithm.
Interesting approach!
3
It depends on the context you’re talking about. From your book’s point of view, requiring that algorithms always end will simplify a lot. For example, it is easier to discuss runtime and computational complexity when programs are finished running. How would you define the running time and computational complexity of a computer program that runs forever, manipulating an infinite stream of data? :)
If the data flow is infinite, then there will always be a routine or procedure to be performed, although the complexity can be determined a priori and I believe that the analysis should not be done in this way. Imagine that a certain procedure is O(log(n)), if the data stream is infinite it will soon run infinitely. Even if it is O(1) if the flow is infinite, we will have O(1) infinite times...
I believe that there is an exact definition of what we are addressing here, and I do not believe that there is a contextual variance.
Mathematics is made up of exact definitions but definitions always depend on the context :) As for your comment, I think you’re getting a little mixed up with infinity. Before assuming that a procedure is O(log(n)) it is necessary to define what the computational complexity of an infinite input algorithm means (which was the rhetorical question I left). It doesn’t make much sense to say "O(1) endlessly"...
The rhetorical question presented is that it leads to the possibility of O(1) infinite times... But in order not to go too far back, you could present another context in which the algorithm has a distinct definition (take a look at the referenced book and see the study on etymology until the application of the term, it may clarify)???
Have a look at https://en.wikipedia.org/wiki/Algorithm_characterizations. There are dozens of definitions you can choose from, depending on your approach... In particular some of the definitions go somewhat in the direction that any set of instructions for a Turing machine would count as an algorithm (even if the Turing machine does not stop for some inputs). As for the part of O(1) infinite times, then try to write a formal definition of what this means :)
I’ll take a look yes :). Imagine you have a method to print a name on the screen and the runtime is O(1). Now imagine that we use an "infinite stream of data", that is (as I understand it) an "infinite list" of names, so this method will be run infinitely often...
0
I believe that every algorithm is finite yes, since even in a situation where the program runs infinitely, some error or the operating system itself can cause a halt. The difference is that the shutdown criterion is not always defined, but there is always the possibility of the system stopping
Browser other questions tagged algorithm terminology
You are not signed in. Login or sign up in order to post.
You can put a more complete quote?
– Maniero
I’ll do better, I’ll expand on the issue and take the reference to the book, which you think @bigown?
– Cold
I don’t know, this is a case that seems to me to be just a matter of interpretation. What’s not wrong with that.
– Maniero
@Cold Would that be the quote? Finiteness: An Algorithm must Always terminate after a Finite number of Steps. Algorithm e satisfies this condition, because after step E1 the value of r is Less than n; so if r != 0, the value of n decreaes the next time step E1 is encountered. A decreasing Sequence of Positive intergers must eventually terminate, so step E1 is executed only a Finite number of times for any Given original values of n. Note, However, that the number of Steps can become arbitrarily large; Certain Huge Choices of m and n will cause step E1 to be executed more than milions times.
– Randrade
@Randrade, it is no longer necessary. And the book in some way answers this question, but always wanted to hear other opinions.
– Cold
Todo algorítimo deve sempre terminar após um número finito de passos?the answer is no to real-time system where certain functions tend to infinity, keep a door in Listen, keep a microphone capturing audio, freeze a frame infinitely (pause your blue ray) ... the subject is disturbing because nothing in life is infinite huahuahua, it is assumed that at some point its function will stop.– ederwander
@bigown Randrade’s quote can be seen and evaluated if in fact it is a question of interpretation :D
– Cold
In the quoted algorithm it is common for TRUTH to be a variable and this process tends to be finite as long as TRUTH is true. At some other time, another process may notify the precesso that Esculta links on port 8080 setting the value of TRUTH as false, causing the next iteration of TRUTH to have false value and not distorting more links on port 8080.
– wryel
@wryel, it is not necessarily a variable. Consider a pure true.
– Cold