No, I didn't say "it's all algorithmic, basta"; I said "so far as we know, it's all algorithmic". Of course it's possible that we'll somehow discover that actually our minds run on magic fairies and unicorns or something, but so far as I can tell all the available evidence is consistent with everything being basically algorithmic. You're the one claiming to know that that isn't so; I invite you to explain how you know.

I haven't claimed that the axioms of arithmetic are derived from something simpler. I have suggested that for all we know, the process by which we found those axioms was basically algorithmic, though doubtless very complicated. (I'm not claiming that that algorithmic process is why the axioms are right. If you're really arguing not about the processes by which discoveries are made but about why arithmetic is the way it is, then we need to have a different discussion.)

it is easily possible to invent new axioms. This is essential for intelligence, yet an AI can't do it, since it only works by its axioms.

I'm afraid this is very, very wrong. Perhaps the following analogy will help: suppose I said "It is easily possible to contemplate arbitrarily large numbers, even ones bigger than 2^32 or 2^64. This is essential for intelligence, yet an AI can't do it, since it only works with 32-bit or 64-bit arithmetic." That would be crazy, right?, because an AI (or anything else) implemented on a hardware substrate that can only do a very limited set of operations can still do higher-level things if it's programmed to. A computer can do arbitrary-precision arithmetic by doing lots of 32-bit arithmetic, if the latter is organized in the right way. Similarly, it can cook up new axioms and rules by following fixed rules satisfying fixed axioms, if the latter are organized in the right way.

And how are these rules determined?

Depends how far back the chain of causation you want to go. There'll be some rules programmed into the computer by human beings. Those were determined by whatever complicated algorithms human brains execute. Those were determined by whatever complicated algorithms human cultures and biological evolution execute. Those were determined by ... etc. As you go further back, you get algorithms with less direct connection to intelligence (ours, or a computer's, or whatever). Ultimately, you end up with whatever the basic laws of nature are, and no one knows those for sure. (But, again, so far as anyone knows they're algorithmic in nature.)

So: no infinite chain, probably (though it's not clear to me that there's anything actually impossible about that); you start with whatever the laws of nature are, and so far as anyone knows they just are what they are. (I suppose you could try to work that up into some kind of first-cause argument for the existence of God, but I should warn you that it isn't likely to work well.)

Really? I think it [emergence] is [magic] ... It seems to me nature is inherently magical.

Oh. Either you're using the word "magical" in a nonstandard way that I don't currently understand, or at least one of us is so terribly wrong about the nature of the universe that further discussion seems unlikely to be helpful.

The universe can't run solely on algorithms, except if you invoke "God did it! He created the first algorithm" or "The first algorithm just appered randomly out of nowhere". I think this statement is ridiculous, but there is no refutation for dogma. If the universe would be so absurd, I could as well be a christian fundamentalist or just randomly do nonsensical things (since it's all random either way).

As a general rule, arguments which rely on having exhausted the hypothesis space are weak. You can't say, "It can't be algorithms, because algorithms don't solve the problem of the first cause." Well, so what? Neither do the straw men you suggest. Neither, indeed, do "emergence" or "magic", which aren't explanations at all. It's one of those hard problems - it doesn't just trouble positions you disagree with.

The axioms of natural numbers can't be determined because they are axioms. If that's not true, "derive 0 is a natural number" and "1 is the succesor of 0" without any notion of numbers.

Again, they cannot be derived within the formal system where they are axioms. They can be determined in a different system which uses distinct axioms or derivation rules. This is, more or less, how you could interpret the parent comment.

The axioms of arithmetic are irreducible simple - to simple to be derived.

Your argument seems to be

1. Humans have derived arithmetics.
2. Arithmetics can't be algorithmically derived from a simpler system.
3. Therefore, humans are not algorithmic.

It seems that you are equivocating in your demands. Your original assertion is that an algorithm can't derive (in this case, meaning invent) formal arithmetics, but the quoted argument supports another claim, namely that the formalisation of arithmetics is the most austere possible. But this claim is not (at least not obviously) relevant to the original question whether intelligence is algorithmic or not. Humans haven't derived formal arithmetics from a simpler formal system. Removing the equivocation, the argument is a clear non-sequitur:

1. Humans have invented arithmetics.
2. Arithmetics can't be simplified.
3. Therefore, humans are not algorithmic.

What else could describe, for example, the emergence of the patterns out of cellular automata rules? It seems to me nature is inherently magical.

What do you mean by magical? Saying "emergence is magical" doesn't look like a description.

I think this statement is ridiculous

I would suggest you to be more careful with such statements. It comes across as confrontational.