Skryptowe języki programowania (np. Python) bądź pośrednie (np. JAVA) są wykonywane przez swoje interpretatory.
Generalnie tak, taki pyinstaller czy podobne narzędzia tworzą execa który zawiera w sobie interpreter oraz kod programu. Są też alternatywne rozwiazania typu https://github.com/shedskin/shedskin które potrafią konwertować jakiś język do C/C++ a potem kompilować go natywnie.
Jeśli chodzi o Javę, to bardzo często jest tak, ze program dystrybuowany jest razem z JRE. Pobierając program pobierasz też wirtualną maszynę Javy. Dzięki temu użytkownik nawet bez zainstalowanej Javy może taki program uruchomić. Na przykład InteliJ na linuxa to nic innego jak JRE właśnie z plikiem wykonywalnym, który tę JRE uruchamia razem z odpowiednią klasą zawierającą metodę main.
W przypadku systemów z rodziny *nix plik wykonywalny to nic innego jak plik, który ma "ustawiony bit "x"". Wówczas system operacyjny pozwoli Ci taki plik uruchomić. A to jak się zachowa w przypadku uruchamiania tego pliku zależy od jego zawartości. Bardzo często pliki, które możesz uruchomić to zwykłe pliki tekstowe. W pierwszej linijce mogą zawierać tzw. "shebang" czyli ciąg znaków informujący shell jak ma taki plik interpretować. Np #!/usr/bin/python w pierwszej linii takiego pliku mówi o tym aby użyć interpretera znajdującego się pod ścieżką /usr/bin/python do przetworzenia zawartości pliku.
Python również jest pośredni tzn. tłumaczony jest na "byte-code" interpretowany przez "Python Virtual Machine".
https://troeger.eu/files/teaching/pythonvm08.pdf
http://security.coverity.com/blog/2014/Nov/understanding-python-bytecode.html