Você não precisa adicionar permissão de execução em arquivos php, instale php5-cli
:
sudo apt-get install php5-cli
E agora, para executar o seu arquivo php, basta digitar:
php test.php
Como alternativa, para realmente torná-lo executável, adicione o php shebang :
#!/usr/bin/php -q
<?php
Print "Hello, World!";
?>
Adicione a permissão de execução no seu arquivo:
chmod +x ./test.php