Linux - No puedo ejecutar programas al hacer doble click sobre él en Ubuntu 16.04

Buenos días a todos.
Lo primero es pedir disculpas porque, realmente, no se si este es el lugar adecuado para incluir esta consulta.
Expongo el tema brevemente, por si alguie puede arrojar luz sobre él.
Resulta que cuando realizo un script en Python sól puedo ejecutarlo o bien desde el IDE o bien desde el terminal de LINUX. Cuando le doy doble click al archivo, se me abre con el GEDIT. Le doy con el botón derecho
para tildar la pestaña "Permitir ejecutar el archivo como uun programa" de la pestaña de propiedades y nada. He probado también lo de darle permisos desde terminal (con lo de "+x") y tampoco.
Si abro una terminal y ejecuto desde ali, entonces funciona a las mil maravillas. El script puede ser de terminal o gráfico, el resultado es el mismo.
Yo estoy utilizando el ubuntu 16.04, pero antes tenia el 14 y tampoco podía.
Y para finalizar, no creo que sea problema de Python porque he hecho el mismo script en C y me pasa lo mismo.
Si alguien sabe algo y puede lanzarme un cable, le estaría agradecido.

En que formato o con que extensión queda guardado el programa?

Si compilas con gcc en C o en C++ si pones el flag del Linker -no-pie se crea un archivo de tipo "Programa (application/x-executable)" y no del tipo "biblioteca compartida (application/x-sharedlib)". Yo tenia el mismo problema en Linux Mint 20.1 y así lo he solucionado.

Ojo si el programa es para usar en terminal no veras nada por pantalla, pero si es modo grafico (Yo uso Qt Studio) te ejecuta el programa con un clic.

Para evitar problemas con la compilación de bibliotecas compartidas o tocar demasiado la configuración del Qt Studio (y romper algo), lo que hago es: Cuando el programa esta listo para distribuir, borro la ultima compilación y edito a mano el fichero Make añadiendo -no-pie en la sección LFLAG, después grabo los cambios en el fichero y hago un Build del programa. Veras que te cambia el icono del programa y que funciona con un clic.

Espero que te sirva.