I agree this is a strawman. You're assuming in step 2 that God would act to stop something from happening because he didn't want it to happen. That pretty much flies in the face of the entire story of scripture and all of human experience. Bad things happen to good people, and sometimes bad people live a good life.

He causes his sun to rise on the evil and the good, and sends rain on the righteous and the unrighteous. Matt 5:45

The entire story from the fall to the crucifixion is an epic saga of things happening in spite of what God wants. Jesus knew that his gift would be destroyed. By your logic he would have chosen not to give it to prevent the rejection, but that isn't what happened.

I think I can show an approach that is quite similar to the halting problem. Here's a thought experiment that my friend once presented to me:

1. Omnipotent being (god 1) creates another omnipotent being (god 2).
2. God 2 may attempt to destroy god 1.
3. God 1 may attempt to prevent its destruction.

There are two possible outcomes:

a) God 2 is omnipotent, so he destroys god 1, so god 1 isn't omnipotent, or

b) God 1 prevents its own destruction, so god 2 isn't able to destroy him, so god 2 is not omnipotent, so god 1 is not omnipotent as he cannot create another omnipotent being (which should be possible for omnipotent being).

I can't think of any flaws in this reasoning and I believe it clearly shows that logic doesn't allow for existence of any all-powerful beings. So either (1) all-powerful God is not constrained by logic, or (2) "being all-powerful" doesn't mean "capable of doing literally anything".

Scenario 1

In this scenario God is truly all-powerful, ie. capable of doing anything, even if it contradicts logic. The paradox in my friend's reasoning isn't solved, but it doesn't have to be solved. The problem with this scenario is explained in the question:

It is possible to say that God does not conform to logic, however if you believe this you must also accept that, from our point of view, we can then say nothing about his nature, his actions or his existence.

On the other hand, omnipotent God could choose to restrict himself to logic in some aspects, so we could actually talk about his attributes. Basically, this approach relies on the assumption that God's nature is (at least partially) undecidable. The halting problem can be solved for some inputs, but not for all of them.

In a nutshell: Logic operates on 0s and 1s, while God operates on real numbers. 0 and 1 are still possible options, though.

Scenario 2

"All-powerful" shouldn't be taken literally. We need a weaker definition of omnipotence. For example:

God is beyond time and He is all-knowing, so he can avoid running into paradoxes. Considering whether God is capable of creating another god is invalid, because He would never do it. Paradoxes are guaranteed to never happen.

To avoid paradoxes the outcome of any possible choice has to be known. So God has to be at least as powerful (in computational sense) as a non-deterministic Turing machine that can solve halting problem in an instant. This is counter-intuitive and hard to grasp, but doesn't break logic.

Limiting God's power even further leads to some problems. For example to lower computational requirements you could require all input to be deterministic, but that would strip humanity from free will. There's also some minimum level of power that we certainly can attribute to God, like the power to violate the laws of physics (Jesus walking on water).

It is, I suppose, conceivable that God is not bound by the laws of logic. But if true further discussion is impossible, as how are we to consider the possibilities except by using logic? I can't imagine how I could prove this either way. Will I present a logical proof that logic always applies? But if logic doesn't apply, then the proof is invalid, and the argument is circular. It is even more difficult to see how one could present a logical argument that logic DOESN'T always apply. So let's accept that God is bound by logic as an axiom.

As others have noted, your paradox example doesn't really work. You appear to be invoking the classic time travel "Run-over grandfather problem": What if you went back in time and killed your grandfather before he had any children? Then you would never be born, and so there would be no one to go back and commit the murder, so your grandfather would live, so you would be born, so there is someone to go back, etc.

But in your example, event A does not cause God to exist, or even cause him to act in a direct sense. Rather, it is the consideration of the consequences of A that causes God to act. If I shoot myself in the foot, it will hurt really bad. Therefore, I do not shoot myself in the foot. I don't need to shoot myself in the foot to know the consequences. I can learn the consequences from hearing of the experiences of others who have shot themselves in the foot, or I could deduce those consequences by considering the nature of bullets, flesh and bone, etc.

Suppose that God is outside of time. He sees all of history as one big panorama. We mortals only perceive a slice of it at any given moment, a slice that moves across the panorama as time passes. But from God's perspective, it's one big picture. He can then draw that picture, considering the implications of every line he draws, extended out as far as he wishes. A human artist drawing a picture of, say, a landscape might say, If I start drawing the base a tree here, I'll need to complete that tree upwards to the top branches, or perhaps draw it abruptly ending in a stump, etc. But he doesn't have to agonize through circular logic like, If I draw the trunk, I'll need to draw the branches, but if I make the branches too wide, then I'll have to redraw the trunk, but if I redraw the trunk ... What would be the catch? He would just draw the tree the way he wanted it. Even if we assume that God can change his mind after seeing how it turns out, so what? So he erases the tree and redraws it the way he wants. He can consider how the tree fits into the landscape and design one big picture meeting all his desired requirements. There's no need to be circular about it at all.

If we assume that God exists within time, but is all-knowing and all-powerful, it doesn't change the model much. He can't draw the whole tree at one time, but he can still decide how he intends to draw it. Actually in practice he could still make a diagram of future history as he intends it to proceed, so in that sense he still can draw the tree all at once. He just can't create the whole history in reality all at once, the plan would have to unfold over time, just as mortals see it.

To take your analogy to computer software: I develop software for a living; I can relate to this. In this case we're looking for the inputs to use to get "good" outputs. So the analogy might be to someone using a mortgage calculator program to analyze a home purchase decision. He puts in the price of the home he's looking at and the interest rate and gets out a monthly payment. He decides that that payment is too high, so he's going to have to settle for a lower-priced home. So he inputs a different home price. He may tinker with this until he finds a combination of home price and monthly payment that he is satisfied with.

This does not lead him into some endless loop of circular logic. The fact that he decided to change the inputs doesn't create an unsolvable self-reference problem, because the user is not part of the program that he is running. He is standing outside feeding inputs. Even if you consider the user to be part of a larger "system" seeking to find an optimal value, there is still no unsolvable self-reference problem. He just plays with values until he gets a satisfactory answer. I don't know if God "plays with" decisions in some "history modelling system" until he gets the desired results, but the concept is the same.

BTW Assuming that God is bound by logic, statements like "God can do anything" should not be taken literally. (When I say that I take the Bible literally, I do not mean that statement literally! The Bible clearly includes poetry, figures of speech, etc. 1 Cor 15:27 says that the word "all" in Psalms 8:6 is not to be taken absolutely literally.) I do not suppose that God can make a triangle with four sides, as that would be logically impossible. You might make such a problem a trick question by redefining the terms in some way, but that's just a trick. By the understood definition of "triangle", it must have exactly three sides. When the Bible says that God is all-powerful, even if taken literally that does not mean that he can do anything. Suppose I told you to draw a four-sided triangle. You reply that this is impossible. So I suggest that you get ten really strong men to help you. Will this make it possible? What if you have the entire output of a nuclear power plant? Clearly more power will not help, because the problem is not lack of power, but logical impossibility.

Sorry for the long answer. Interesting question on which, I am sure, lots more could be said.

You're assuming that self-reference is required somehow, that God has to "evaluate himself" (whatever that means) when making decisions, and that his decision-making is based solely on observation and not on any sort of predictive ability. There's a much simpler conceptual model:

"Something important is about to happen. There are three possible outcomes. Predict which of the three is most favorable--which will necessarily be a correct prediction due to omniscience--and cause that one to occur." No self-reference required.

The God of the Bible states "I declare the end from the beginning." In comparing God to an algorithm, you go against the fundamental claims of God --that is, you create a straw man to knock over.

God is not an algorithm, waiting for an asynchronous user event or for some unseen input data. God is the author of the data and thus by necessity of being its creator, it is sanitized to be within the exact ranges on which He wishes his state machine to operate. God has created the algorithm to run on the data. God has created the machine on which the algorithm runs and into which the input data goes. The analogy is broken from the beginning.

Edit: What you're arguing against in your question is a form of Molinism, not historical perspectives of Man's free will and God's sovereignty. In this regard, you are entirely correct which is why I struggle finding correctness in Molinism.

I believe you miss a few key points about the halting problem.

1. Just because there is no algorithm that can decide for every input program if it will halt, does not mean that no algorithms exist for any given input. See: Are Impossibility Proofs Possible?- Halting Problem for examples.

   You assume that God would have to function over every single conceivable input, where it may be that the number of inputs itself is fixed to some subset.

2. The problem can be reliably solved by people for a given subset of programs. The wikipedia introduction to the Halting problem gives two trivial examples of such.

   The halting problem relies on the fact that no algorithm could examine every branch of any significantly complex program, similar in a sense to the inability of the computer to compute every legal move in a chess game.

   Simply assuming that God is all knowing immediately demonstrates that He would know every branch of execution for the Universe and would by definition be able to decided if it would halt or not.

3. Your assumption relies on the fact that once God acts He would need to evaluate the outcome.

   This has never been a requirement of the halting problem that I am aware of. Nothing requires the output of the algorithm to be fed back into the algorithm, but even if you can demonstrate a reasonable formulation of the problem that meets that requirement, God is not required to act. Meaning that Ge is not required to intervene to make the Universe more to his liking.

4. There exist modifications to even simple Turing machines which, as it turns out, enables them to solve the Halting problem.

   As the following Stanford article on Computation in Physical Systems states

This allows infinitely accelerating Turing machines to compute functions, such as the halting function, that are Turing-uncomputable.

So, simply by removing time as a factor, computability limitations are removed. Clearly refuting your claim that "if you know about the halting problem, you will know that it is not based on time".

There are an awful lot of assumptions here.

1. There is but one way to stop B
2. There is no way to stop B if A has happened
3. Etc

But it mainly boils down to this main flaw in the logic:

Event A no longer happened and therefore God would never intervene in the first place. Go to 1.

Being all knowing God would of course be able to know the possibility of A causing B. Thus the possibility of B happening is cause enough to stop A.