Post var en föregångsman inom matematikens grundvalar med sina studier från 1920-talet av avgörbarheten hos logiska system. Vidare framlade han 1936 en beräkningsmodell, Post-maskinen, som är ekvivalent med konstruktioner som beskrivits av Turing och Church.