This is very dependent on the child, as are all questions of this sort, but 5-6 is certainly possible.
My children, now eight and nine, were first exposed to programming in a meaningful way at around the age of 4-5. We started with simple games that are "programming lite", which basically involve the child creating a "program" either to get a piece from one place to another with instructions, or in one case "programming" the parent to do whatever the child wants them to. That teaches the concept of step-by-step instructions, boolean logic, and even functions (you can make a "function" of several instructions, then call that function instead of repeating the lines). They also had programmable robots (actual robots with iPad apps that let them give them repeatable instructions with a block-based language, including logic gates and loops and functions). Those are very fun at that age.
This led us to recognize that they - and particularly the younger - were interested in programming, so we continued along those lines. At around six, Scratch or similar block-based languages are very accessible. They used them to both build simple programs and to see others' much more complex programs in action. Mostly we didn't push anything here - they had a few books that guided them through the initial steps, but for the most part this was about learning to have fun with programming and do whatever silly thing they wanted to do, even if it was fill the screen with cats meowing, or make a ball that bounced indefinitely.
Around seven, both children started learning Python. The oldest got bored with it to some extent, but the youngest really took to it and programs on his own for fun, or to solve problems (like randomizing choices for music lessons). Although they're not able to program anything complex yet, they understand the basic concepts and have a desire to learn more - which we will certainly enable as much as possible!
Pushing, though, doesn't really work at this age, and I don't recommend it. Expose them to programming and see if they like it - this is very possible at five or six, either through games or through beginning programming experiences with block-based languages; and then pay attention for when they're ready to go to the next step. My kids are both relatively early readers, which meant I could teach them Python at seven - but I'd suspect many kids need to wait a few more years before their fluency is sufficient. Scratch/etc. are great since they don't require as much reading - you can learn what the blocks are by shape recognition.