Think of a computer as a Turing Machine--this idea is a model of computation, and all of modern computing is based on the Turing-Church thesis.
Machine and program can be interchangeable—at the end of the day, it's all algorithms, whether hard coded in the form of microchip, or in the form of software. (Any microchip can be emulated as software.)
Pre-modern computers were mechanical in popular sense. Examples include Babbage's
difference engine, and mechanical calculators in general. These led to programmable mechanical calculators and electromechanical computers such as IBM's Harvard Mark I, based on Babbage's notion of an Analytic Engine.
In this context, Machine Learning may also connote software that runs on a machine (hardware) as opposed to human/animal learning, which utilizes a biological medium.
The etymology of "mechanics", and by extension, "machine" is worth looking at.
Mechanema is instructive in that math and engineering can be understood as the "trick to doing things". (Machination is not pejorative in this sense, as "noun of action from past participle stem of machinari 'contrive skillfully, to design; to scheme, to plot,'"—one can plot the course of a celestial body.)
Early uses of the mech- root
Aristotle's Μηχανικά ("Mechanical Problems"*)
Euler's Mechanica (Euler was referring to Classical Mechanics, an analytic and predictive science made possible by calculus, which is based on functions.)