According to the website and User Guide, the minimum required version of PHP is 5.0 or higher for EE.
ExpressionEngine 2.1.3 requires PHP 5.1.6 or higher. So I think it’s good to mention this on the site and in the User Guide as for new customers it might be a criteria to select appropriate hosting.