Nope, technically it has to be an infinite machine, otherwise it's just an over complicated finite state machine and proving termination in those is trivial. I

Nope, technically it has to be an infinite machine, otherwise it's just an over complicated finite state machine and proving termination in those is trivial. I/O (except to bounded sources like disks) could probably save you, but the proof will be harder.