The game of arithmetic hide-and-seek

Angel tries guess where Demon hides now.

Here is a mathematical problem I've made recently. It could seem unsolvable at first, but there is a solution, and a simple one!

Update: see solution here.

The problem

Angel and Demon are playing the game of arithmetic hide-and-seek. The game is played on a linear "field" of numbered cells, going infinitely both in positive and negative directions.

Before the play, Demon conceives a formula, using 5 operations: addition \(+\), subtraction \(-\), division \(/\), multiplication \(*\) and powering \(x^y\); any integer numbers and variable \(k\). He never shows that formula to Angel.

Some of possible formulas are: \(666+k\); \(k^2-3k\); \(k^k\); \(2^k/k\) or just \(5\).

The game is played in turns. On each turn, first Demon moves. He substitutes current turn number for \(k\) in his formula. I.e. \(k=1\) on the first turn, \(k=2\) on the second etc. Then he evaluates it, rounds the result down to the nearest integer (example: 17/5 = 3.6 rounds to 3), and hides in that cell.
If the formula has no numeric value, like \(1/(k-5)\) when \(k=5\), then Demon hides in the cell 0.

Then Angel takes action. He does not see Demon, but on each turn he can check one cell. If he finds Demon there, then Angel wins. Otherwise, the game continues to the next turn.

Clearly, there is no way for the demon to win, but he could hope to hide forever.

Propose a winning strategy for Angel, and thus show that Angel can always win in a finite number of attempts.

Additional questions

1. Estimate the asymptotic growth rate of the distance of Angel's search.
2. Is the problem solvable, if instead of a formula Demon uses an ideal computer (Turing machine?)