This is quite a difficult question to answer. I would comment if I could.
The first problem is that you have not defined what you mean by a computer? Are you talking about the electrical based computers we know today or are you also including mechanical computers in your question? Here's a wiki link about the Difference Engine. The difference engine is completely mechanical but you can still technically 'program' it although it does not directly follow the paradigms of today.
Most parts of your question relate to one specific problem: How does the processing unit of a computational device work in a general way in accordance to the modern idea of software? I will give a general overview of what processor do.
A computer has three general operations: input (The input the user puts in, which includes data and what operation is wanted to be done), processing (the processor taking the input and operating on it) and output (what information is returned to the user). So what is inputted into a computer at the lowest level is some data and what is called an op-code or instruction. This is instruction is part of a collection stored in the processor (either electronically or via some other physical means) which has a defined algorithm associated with it. These instructions are considered 'basic' or low level. When something much more complicated is required to be processed, it is broken down into small parts which use these instructions to produce the desired computation in the end. Mechanical processors, specifically gearing based systems work in a similar way but accept input differently. The gears shift according to an algorithm to produce a result from a specific sequence of gear shifts initially (which is the input).
Here's a link to a Intel Lesson Series on Microprocessors
Another explanation of the CPU
From what I can gather the software you are talking about are the programs you see running on a computer. These are considered to be high level software, which are very complex when looking at this software from the perspective of a processor. Essentially the tools used to make this software and the software itself is broken down into a set of instructions for the processor to process at some point in the execution chain. With modern software there are many layers of abstraction to get from the processor to what the user sees. See this Wikipedia article about abstraction (It's the most comprehensive I could find): https://en.wikipedia.org/wiki/Abstraction_(computer_science)
Modern compilers such as gcc take human readable code and turn that into executable code which the operating system then executes. During execution the operating system will call processor instructions (which is a few abstraction levels down) in accordance to the executable code which the compiler produced.
