<p>There has been a recent line of work on <em>computable learnability</em>:</p>
<p><a href="http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf" rel="nofollow noreferrer">http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf</a></p>
<p><a href="http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf" rel="nofollow noreferrer">http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf</a></p>
<p>This seems to be exactly the sort of thing you're asking about. You also ask about the implications <span class="math-container">$1\implies 2$</span> and <span class="math-container">$2\implies 3$</span>. The latter is indeed trivial: if <em>a particular</em> learning rule (ERM) succeeds, then certainly <em>some</em> rule does.</p>
<p><span class="math-container">$1\implies 2$</span> holds for all classes, not just finite ones. Again, it's pretty straightforward: uniform convergence means that the behavior of any <span class="math-container">$f\in F$</span> on the sample will be, with high probability, representative of its behavior on the whole space -- and hence minimizing the sample error is a valid learning rule.</p>
<p>Your biggest issue seems to be with an effective procedure for performing ERM on given data. We CS people handle this difficulty as follows: Either you're in the real world of finite-precision measurements, in which case everything is finite, and no philosophical issues arise. Or, alternatively, if you insist on infinite-precision data, then you must allow me infinite-precision computation as well. For example, I can pose SVM as a quadratic program and guarantee convergence to within a specified <span class="math-container">$\epsilon$</span> precision in finite time. If <span class="math-container">$\epsilon$</span> is sufficinetly smaller than the margin, I can still guarantee generalization.</p>

CC BY-SA 4.0
2021-08-29T10:52:00.710Z
Thank you for the answer. I still do not see how it has anything to do with precision. If class of functions is infinite, ERM rule needs to find minimum from an infinite set. It doe not matter how long you try functions one by one, you can not guarantee that the solution is has some precision: unseen function may be much better that anything seen.
Marina
CC BY-SA 4.0
2021-08-29T10:57:02.043Z
the other person said that in this section about PAC learning the word "leaning algorithm" means "function".   Is this the case? So, the "algorithm" (function) may exist, but it is not "implementable". Is this how you understand it? The term "implementable" appears in chapter 6 of this book.
Marina
CC BY-SA 4.0
2021-08-29T11:01:40.060Z
I noticed, in the articles you refer to there is the term "computable learners". It would imply that there may be un-computable learners. So, the ERM rule may be un-computable sometimes. And "PAC learnable" may not be "PAC computable learnable". Is this how you understand it?
Marina
CC BY-SA 4.0
2021-08-29T11:06:08.323Z
They write: " We thus propose the notion of CPAC learnability,
by adding some basic computability requirements into a PAC learning framework.". Exactly!  Thank you very much for pointing it out.
Marina
CC BY-SA 4.0
2021-08-29T11:25:35.613Z
From the same article. They write: " The
common statistical learning theory, in which we have the fundamental characterization of PAC learnability by the finiteness of the VC-dimension, allows for the learners to be arbitrary functions". What the authors (including one of the authors of this artile) call "learning algorithm" in this part of the book is "arbitrary function". What they call "learning algorithm" in other parts of the book means "description of a computer program". They never let us know when they switched from one concept to another with the same name.
Marina
CC BY-SA 4.0
2021-08-29T12:06:05.933Z
There's a lot to unpack here. Let's start with the first comment, "I still do not see how it has anything to do with precision." Did you understand my SVM example? The collection of all hyperplanes is an (uncountably) infinite class. But if I can assume access to an infinite-precision quadratic program solver, I can find the optimal hyperplane. So far so good?
Aryeh
CC BY-SA 4.0
2021-08-29T12:32:23.753Z
With SVM there is no problem. With finding minimum of an arbitrary infinite set there is a problem.
Marina
CC BY-SA 4.0
2021-08-29T12:36:43.827Z
OK, so you're asking about the distinction between a *learning rule* vs. an *effective learning algorithm*. This may warrant a separate answer, shall I?
Aryeh
CC BY-SA 4.0
2021-08-29T13:04:04.170Z
The term "effective learning algorithm" is never mentioned in this book, as far as I know. The same about "learning rule". They always talk about "learning algorithm". In the beginning the book they say the goal is to describe how to make a machine to learn. Learning algorithm is supposed to be something used by a machine. So, in definition of PAC learnable they say "algorithm exists". I though it is computer algorithm. But they mean "function". This is the issue. Do you have an answer? I would very welcome it. Thanks.
Marina
CC BY-SA 4.0
2021-08-29T15:20:35.833Z
OK, I gave it a shot...
Aryeh
CC BY-SA 4.0
2021-08-29T07:44:56.837Z
2021-10-06T13:17:51.920Z
2021-10-06T13:17:51.920Z
Aryeh
<p>I know it's generally considered bad form to add another answer on top of an accepted one, but this one is by special request and it's a topic that deserves its own discussion.</p>
<p>The topic is: Effective learning algorithms vs. learning rules. A learning rule is simply a mathematically well-defined mapping from a labeled sample to some function class. (The mapping has to satisfy some minimal measurability properties, see Remark 4.10 here
<a href="https://arxiv.org/pdf/1906.09855.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1906.09855.pdf</a> ). However, the mapping need not be effectively computable by a Turing machine. For example, the learning &quot;algorithm&quot; described in the Benedek-Itai paper &quot;Learnability with respect to fixed distributions&quot; (<a href="https://dl.acm.org/doi/10.5555/117115.117118" rel="nofollow noreferrer">https://dl.acm.org/doi/10.5555/117115.117118</a>) has the form
<a href="https://i.sstatic.net/N3pCd.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/N3pCd.png" alt="enter image description here" /></a>,
where <span class="math-container">$n_D$</span> is an <span class="math-container">$\ell_1$</span> covering number of the concept class <span class="math-container">$C$</span> w.r.t. the distribution <span class="math-container">$D$</span>. This is a well-defined mapping from samples to classifiers, but not an effective algorithm. To obtain the latter, one needs to carefully specify a <em>representation</em>. Section 1.2.2 of the Kearns-Vazirani book (<a href="https://mitpress.mit.edu/books/introduction-computational-learning-theory" rel="nofollow noreferrer">https://mitpress.mit.edu/books/introduction-computational-learning-theory</a>) addresses the topic of representation in detail. Once a representation has been specified, one can talk about effective algorithms and even exact runtimes.</p>

CC BY-SA 4.0
2021-08-29T15:47:35.170Z
Thank you. The book was published in 1994. Would you recommend this book for the study of statistical learning theory rather than "Understanding machine learning"?
Marina
CC BY-SA 4.0
2021-08-29T15:53:05.520Z
I'd say K+V is quite a bit more dated -- certainly, the chapter on boosting is rather outdated. Also, learning automata, membership/equivalence queries have kind of fallen by the wayside (and I say this as someone who spent a good few years on automata learning). The first 3 chapters are still "modern". I'd say the Mohri et al. book (https://mitpress.mit.edu/books/foundations-machine-learning) is more modern and user-friendly.
Aryeh
CC BY-SA 4.0
2021-08-29T16:02:16.027Z
In Mohri,  there is practically the same definition of PAC learnable: "there exists an algorithm" without strict definition of algorithm. The newest article with Ben-David coauthor has very strict definitions. So, I will use it for my work.  I need a mathematically-friendly text, and the latest articles you quoted are what I need. Thanks.
Marina
CC BY-SA 4.0
2021-08-29T16:03:10.133Z
yes, ppl are a bit loose with "algorithm" vs. "learning rule". I reserve alg strictly for Turing-machine implementable rules.
Aryeh
CC BY-SA 4.0
2021-08-29T15:20:19.567Z
2021-08-29T20:38:33.813Z
2021-08-29T20:38:33.813Z
Aryeh
<p>I am reading the book &quot;Understanding Machine Learning&quot; by Shai Shalev-Shwartz and Shai Ben-David.
The theorem 6.7 has several equivalent statements for a class of functions <span class="math-container">$H$</span>. The first three are:</p>
<ol>
<li><span class="math-container">$H$</span> has the uniform convergence property.</li>
<li>Any ERM rule is a successful agnostic PAC learner for <span class="math-container">$H$</span>.</li>
<li><span class="math-container">$H$</span> is agnostic PAC learnable.</li>
</ol>
<p>For the proof of inference  1 <span class="math-container">$\rightarrow$</span> 2 the book refers to the chapter 4, where the results are proven only for finite classes. It says, inference 2 <span class="math-container">$\rightarrow$</span> 3 is trivial. Is it?</p>
<p>ERM rule is the algorithm which, given a sample <span class="math-container">$S$</span>,  finds  hypothesis with minimal empirical risk among all functions in <span class="math-container">$H$</span>. If the ERM rule for a given class of functions exists, and it is a successful agnostic PAC learner, then <span class="math-container">$H$</span> is agnostic PAC learnable, of course.</p>
<p>But is there a proof that ERM rule exists for every class of functions, or is there a way to see that the theorem is true even if the class of functions does not have a ERM rule?</p>

CC BY-SA 4.0
2021-08-28T08:54:33.453Z
why doesn't erm rule always exist? you get a finite sample, so just choose something with $0$ mistakes if it exists; otherwise choose something with $1$ mistake; etc.. If you're worried about the axiom of choice or something like that, then that's another story...
mathworker21
CC BY-SA 4.0
2021-08-28T11:22:14.003Z
@mathworker21 How do you chose something that has no mistakes from an infinite class of functions? The class may not even have a function which has no mistakes. I am worried  about existence of an algorithm which finds a minimum from an infinite set.
Marina
CC BY-SA 4.0
2021-08-28T14:16:21.867Z
"How do you choose something that has no mistakes from an infinite class of functions?" Just choose one. Unless you're worried about axiom of choice (which you should say if you are). "The class may not even have a function which has no mistakes." I addressed this in my last comment. "I am worried about existence of an algorithm which finds a minimum from an infinite set." The relevant set is finite; you only get a finite number of samples. True there could be an infinite class of functions, but I don't see the relevance.
mathworker21
CC BY-SA 4.0
2021-08-28T14:53:49.037Z
@mathworker21 "The relevant set is finite". No . The relevant set is infinite: this is the class of functions, from which we need to chose one function with the minimal number of errors. You know, like class of all polynomials of degree up to k.
Marina
CC BY-SA 4.0
2021-08-28T14:56:31.043Z
I don't get your issue. Just choose a function. If you ask me to choose a polynomial of degree up to 100 that has a root at $x=1$, I'll choose $(x-1)^{30}$.
mathworker21
CC BY-SA 4.0
2021-08-28T15:01:00.043Z
OK. We are dealing with machine learning here. Given is finite training set $S$, the sequence of $m$ pairs $\langle x_i, y_i \rangle$. Given is a class of functions $F,$ potentially infinite. For each function the error is evaluated by the rule $L(f, S) = \sum_i I(f(x_i) \neq y_i).$ The goal is to find a function $h = \arg \min_{f \in F} L(f, S).$
Marina
CC BY-SA 4.0
2021-08-28T15:01:54.670Z
Yea, just choose/find one. It obviously exists. Is your issue with the axiom of choice?
mathworker21
CC BY-SA 4.0
2021-08-28T15:03:32.327Z
How do you chose a function which solves the problem from the infinite set? Please, describe the algorithm. You know what algorithm is, right? Thank you.
Marina
CC BY-SA 4.0
2021-08-28T15:05:34.983Z
No I don't. We're talking about theoretical machine learning. The theorem you ask about is completely theoretical with no reference to algorithms.
mathworker21
CC BY-SA 4.0
2021-08-28T15:07:45.407Z
We are talking about the FTSL, which states that "Every ERM rule is succseeful PAC learner" is equivalent with "$H$ is PAC learnable". The proof relies on existence of algorithm called ERM rule.
Marina
CC BY-SA 4.0
2021-08-28T15:09:15.390Z
Definition of "PAC learnable" includes "existence of algorithm". So, you need to know what algorithm is to answer the question.
Marina
CC BY-SA 4.0
2021-08-28T15:15:40.427Z
An algorithm is just a function, at least for the first part of the book (which has as part of the title "from theory to algorithms"). Weirdly, I can't find the definition of "algorithm" given. I'm nearly certain it is just a function for the purposes of the first part of the book
mathworker21
CC BY-SA 4.0
2021-08-28T15:17:24.120Z
There is no definition. The algorithm is a sequence of steps, each of which is elementary and practically possible. This is my kind of definition. Sorry. There is nothing better I think. With numbers, algorithm is something you can program in a computer language. Can you program?
Marina
CC BY-SA 4.0
2021-08-28T15:20:34.137Z
"The algorithm is a sequence of steps, each of which is elementary and practically possible." Lol, the book is completely mathematically rigorous; what you said is not. It's a math book; at least the first half is. I am able to program.
mathworker21
CC BY-SA 4.0
2021-08-28T15:21:15.263Z
Also, there is stuff better. The definition of "algorithm" in some parts of computer science is made rigorous using, for example, Turing Machines...
mathworker21
CC BY-SA 4.0
2021-08-28T15:21:28.910Z
Great. Please describe the program of ERM rule for an infinite class.
Marina
CC BY-SA 4.0
2021-08-28T15:22:46.863Z
Does "infinite" even exist in the real world?  I don't think you can program for infinite stuff. I don't know of such a program, but luckily, the definition of "algorithm" the book is using is "function".
mathworker21
CC BY-SA 4.0
2021-08-28T15:23:23.127Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/129038/discussion-between-marina-and-mathworker21).
Marina
CC BY-SA 4.0
2021-08-29T11:31:06.180Z
@mathworker21 You were exactly right! From the horse's mouth: http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf " The
common statistical learning theory, in which we have the fundamental characterization of PAC
learnability by the finiteness of the VC-dimension, allows for the learners to be arbitrary functions."
Marina
<machine-learning><pac-learning>
Some issues with proof of Fundamental Theorem of Statistical learning
Marina
# Some issues with proof of Fundamental Theorem of Statistical learning

(Asked by: username_0 on 2021-08-28)

I am reading the book "Understanding Machine Learning" by Shai Shalev-Shwartz and Shai Ben-David.
The theorem 6.7 has several equivalent statements for a class of functions $H$. The first three are:

1. $H$ has the uniform convergence property.
2. Any ERM rule is a successful agnostic PAC learner for $H$.
3. $H$ is agnostic PAC learnable.

For the proof of inference 1 $\rightarrow$ 2 the book refers to the chapter 4, where the results are proven only for finite classes. It says, inference 2 $\rightarrow$ 3 is trivial. Is it?

ERM rule is the algorithm which, given a sample $S$, finds hypothesis with minimal empirical risk among all functions in $H$. If the ERM rule for a given class of functions exists, and it is a successful agnostic PAC learner, then $H$ is agnostic PAC learnable, of course.

But is there a proof that ERM rule exists for every class of functions, or is there a way to see that the theorem is true even if the class of functions does not have a ERM rule?

**Tags:** machine-learning, pac-learning
> **Comments:**
> **username_1**: why doesn't erm rule always exist? you get a finite sample, so just choose something with $0$ mistakes if it exists; otherwise choose something with $1$ mistake; etc.. If you're worried about the axiom of choice or something like that, then that's another story...  
> **username_0**: @mathworker21 How do you chose something that has no mistakes from an infinite class of functions? The class may not even have a function which has no mistakes. I am worried  about existence of an algorithm which finds a minimum from an infinite set.  
> **username_1**: "How do you choose something that has no mistakes from an infinite class of functions?" Just choose one. Unless you're worried about axiom of choice (which you should say if you are). "The class may not even have a function which has no mistakes." I addressed this in my last comment. "I am worried about existence of an algorithm which finds a minimum from an infinite set." The relevant set is finite; you only get a finite number of samples. True there could be an infinite class of functions, but I don't see the relevance.  
> **username_0**: @mathworker21 "The relevant set is finite". No . The relevant set is infinite: this is the class of functions, from which we need to chose one function with the minimal number of errors. You know, like class of all polynomials of degree up to k.  
> **username_1**: I don't get your issue. Just choose a function. If you ask me to choose a polynomial of degree up to 100 that has a root at $x=1$, I'll choose $(x-1)^{30}$.  
> **username_0**: OK. We are dealing with machine learning here. Given is finite training set $S$, the sequence of $m$ pairs $\langle x_i, y_i \rangle$. Given is a class of functions $F,$ potentially infinite. For each function the error is evaluated by the rule $L(f, S) = \sum_i I(f(x_i) \neq y_i).$ The goal is to find a function $h = \arg \min_{f \in F} L(f, S).$  
> **username_1**: Yea, just choose/find one. It obviously exists. Is your issue with the axiom of choice?  
> **username_0**: How do you chose a function which solves the problem from the infinite set? Please, describe the algorithm. You know what algorithm is, right? Thank you.  
> **username_1**: No I don't. We're talking about theoretical machine learning. The theorem you ask about is completely theoretical with no reference to algorithms.  
> **username_0**: We are talking about the FTSL, which states that "Every ERM rule is succseeful PAC learner" is equivalent with "$H$ is PAC learnable". The proof relies on existence of algorithm called ERM rule.  
> **username_0**: Definition of "PAC learnable" includes "existence of algorithm". So, you need to know what algorithm is to answer the question.  
> **username_1**: An algorithm is just a function, at least for the first part of the book (which has as part of the title "from theory to algorithms"). Weirdly, I can't find the definition of "algorithm" given. I'm nearly certain it is just a function for the purposes of the first part of the book  
> **username_0**: There is no definition. The algorithm is a sequence of steps, each of which is elementary and practically possible. This is my kind of definition. Sorry. There is nothing better I think. With numbers, algorithm is something you can program in a computer language. Can you program?  
> **username_1**: "The algorithm is a sequence of steps, each of which is elementary and practically possible." Lol, the book is completely mathematically rigorous; what you said is not. It's a math book; at least the first half is. I am able to program.  
> **username_1**: Also, there is stuff better. The definition of "algorithm" in some parts of computer science is made rigorous using, for example, Turing Machines...  
> **username_0**: Great. Please describe the program of ERM rule for an infinite class.  
> **username_1**: Does "infinite" even exist in the real world?  I don't think you can program for infinite stuff. I don't know of such a program, but luckily, the definition of "algorithm" the book is using is "function".  
> **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/129038/discussion-between-marina-and-mathworker21).  
> **username_0**: @mathworker21 You were exactly right! From the horse's mouth: http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf " The common statistical learning theory, in which we have the fundamental characterization of PAC learnability by the finiteness of the VC-dimension, allows for the learners to be arbitrary functions."  

---

## 2 answers

### Answer by username_2 on 2021-08-29. Score: 4 | Accepted answer

There has been a recent line of work on *computable learnability*:

<http://proceedings.mlr.press/v117/agarwal20b/agarwal20b.pdf>

<http://www.learningtheory.org/colt2021/virtual/static/images/agarwal21b.pdf>

This seems to be exactly the sort of thing you're asking about. You also ask about the implications $1\implies 2$ and $2\implies 3$. The latter is indeed trivial: if *a particular* learning rule (ERM) succeeds, then certainly *some* rule does.

$1\implies 2$ holds for all classes, not just finite ones. Again, it's pretty straightforward: uniform convergence means that the behavior of any $f\in F$ on the sample will be, with high probability, representative of its behavior on the whole space -- and hence minimizing the sample error is a valid learning rule.

Your biggest issue seems to be with an effective procedure for performing ERM on given data. We CS people handle this difficulty as follows: Either you're in the real world of finite-precision measurements, in which case everything is finite, and no philosophical issues arise. Or, alternatively, if you insist on infinite-precision data, then you must allow me infinite-precision computation as well. For example, I can pose SVM as a quadratic program and guarantee convergence to within a specified $\epsilon$ precision in finite time. If $\epsilon$ is sufficinetly smaller than the margin, I can still guarantee generalization.

> **Comments:**
> **username_0**: Thank you for the answer. I still do not see how it has anything to do with precision. If class of functions is infinite, ERM rule needs to find minimum from an infinite set. It doe not matter how long you try functions one by one, you can not guarantee that the solution is has some precision: unseen function may be much better that anything seen.  
> **username_0**: the other person said that in this section about PAC learning the word "leaning algorithm" means "function".   Is this the case? So, the "algorithm" (function) may exist, but it is not "implementable". Is this how you understand it? The term "implementable" appears in chapter 6 of this book.  
> **username_0**: I noticed, in the articles you refer to there is the term "computable learners". It would imply that there may be un-computable learners. So, the ERM rule may be un-computable sometimes. And "PAC learnable" may not be "PAC computable learnable". Is this how you understand it?  
> **username_0**: They write: " We thus propose the notion of CPAC learnability, by adding some basic computability requirements into a PAC learning framework.". Exactly!  Thank you very much for pointing it out.  
> **username_0**: From the same article. They write: " The common statistical learning theory, in which we have the fundamental characterization of PAC learnability by the finiteness of the VC-dimension, allows for the learners to be arbitrary functions". What the authors (including one of the authors of this artile) call "learning algorithm" in this part of the book is "arbitrary function". What they call "learning algorithm" in other parts of the book means "description of a computer program". They never let us know when they switched from one concept to another with the same name.  
> **username_2**: There's a lot to unpack here. Let's start with the first comment, "I still do not see how it has anything to do with precision." Did you understand my SVM example? The collection of all hyperplanes is an (uncountably) infinite class. But if I can assume access to an infinite-precision quadratic program solver, I can find the optimal hyperplane. So far so good?  
> **username_0**: With SVM there is no problem. With finding minimum of an arbitrary infinite set there is a problem.  
> **username_2**: OK, so you're asking about the distinction between a *learning rule* vs. an *effective learning algorithm*. This may warrant a separate answer, shall I?  
> **username_0**: The term "effective learning algorithm" is never mentioned in this book, as far as I know. The same about "learning rule". They always talk about "learning algorithm". In the beginning the book they say the goal is to describe how to make a machine to learn. Learning algorithm is supposed to be something used by a machine. So, in definition of PAC learnable they say "algorithm exists". I though it is computer algorithm. But they mean "function". This is the issue. Do you have an answer? I would very welcome it. Thanks.  
> **username_2**: OK, I gave it a shot...  

---

### Answer by username_2 on 2021-08-29. Score: 1

I know it's generally considered bad form to add another answer on top of an accepted one, but this one is by special request and it's a topic that deserves its own discussion.

The topic is: Effective learning algorithms vs. learning rules. A learning rule is simply a mathematically well-defined mapping from a labeled sample to some function class. (The mapping has to satisfy some minimal measurability properties, see Remark 4.10 here
<https://arxiv.org/pdf/1906.09855.pdf> ). However, the mapping need not be effectively computable by a Turing machine. For example, the learning "algorithm" described in the Benedek-Itai paper "Learnability with respect to fixed distributions" (<https://dl.acm.org/doi/10.5555/117115.117118>) has the form
[![enter image description here](https://i.sstatic.net/N3pCd.png)](https://i.sstatic.net/N3pCd.png),
where $n\_D$ is an $\ell\_1$ covering number of the concept class $C$ w.r.t. the distribution $D$. This is a well-defined mapping from samples to classifiers, but not an effective algorithm. To obtain the latter, one needs to carefully specify a *representation*. Section 1.2.2 of the Kearns-Vazirani book (<https://mitpress.mit.edu/books/introduction-computational-learning-theory>) addresses the topic of representation in detail. Once a representation has been specified, one can talk about effective algorithms and even exact runtimes.

> **Comments:**
> **username_0**: Thank you. The book was published in 1994. Would you recommend this book for the study of statistical learning theory rather than "Understanding machine learning"?  
> **username_2**: I'd say K+V is quite a bit more dated -- certainly, the chapter on boosting is rather outdated. Also, learning automata, membership/equivalence queries have kind of fallen by the wayside (and I say this as someone who spent a good few years on automata learning). The first 3 chapters are still "modern". I'd say the Mohri et al. book (https://mitpress.mit.edu/books/foundations-machine-learning) is more modern and user-friendly.  
> **username_0**: In Mohri,  there is practically the same definition of PAC learnable: "there exists an algorithm" without strict definition of algorithm. The newest article with Ben-David coauthor has very strict definitions. So, I will use it for my work.  I need a mathematically-friendly text, and the latest articles you quoted are what I need. Thanks.  
> **username_2**: yes, ppl are a bit loose with "algorithm" vs. "learning rule". I reserve alg strictly for Turing-machine implementable rules.  

---

