Return to Answer

The above can be illustrated by the graphic: alt text http://storage2.static.itmages.ru/i/12/0529/h_1338260211_3196579_1cf8844971.png

Here upper semi-flow (flow of cos(cos z)) ) is blue, lower semi-flow is red, real part of the flow is yellow, imaginable part of the flow is green. All flows are taken as point z=1.

alt text http://storage3.static.itmages.ru/i/12/0529/h_1338260611_9481992_3ed5df167f.png Here blue is the real part and red is the imagine part.

We can verify that the half-iterate repeated twice $\Phi(1/2,\Phi(1/2,z))$ (blue) follows cosine (red) quite well at least at positive half-periods: alt text http://storage4.static.itmages.ru/i/12/0529/h_1338260827_7686578_7b7eaac3d1.png

A modified function, iterated twice gives cosine in all positive half-plane: $$\Phi_{mod}(x,z)=\cases { \operatorname{sgn}(\Re(z))\Phi(x,z), & \text{if } \Re(z)<0 \cr \text{sgn}(\Re(z)) \operatorname{sgn}(\cos (\Re(z))) \Phi(x,z), & \text{if } \Re(z)>0} $$

$\Phi_{mod}(1/2,\Phi_{mod}(1/2,z))$ alt text http://storage4.static.itmages.ru/i/12/0529/h_1338268623_1775800_e3a2f72aad.png

A Mathematica notebook that does all the above is as follows:

f[x_, z_] := If[x >= 0, Nest[Cos, z, 2 x], Nest[ArcCos, z, -2 x]]
n := 20
s := 12
Ni[x_, z_] := \!\(
\*UnderoverscriptBox[\(\[Sum]\), \(m = 
    0\), \(n\)]\((Binomial[x + 1, m] \(
\*UnderoverscriptBox[\(\[Sum]\), \(k = 0\), \(m\)]\((
\*SuperscriptBox[\((\(-1\))\), \(k - m\)] Binomial[m, k] f[k - 1, 
        z])\)\))\)\)

Semi2[x_, z_] := Ni[x/2, z]
Semi1[x_, z_] := ArcCos[Semi2[x + 1, z]]
FP := Evaluate[N[FixedPoint[Cos, 1.0]]]
(*Flow[x_,z_]:=If[Divisible[x,2],f[x/2,z],Cos[f[(x-1)/2]]]

Flow1[x_,z_]:=\!\(
\*UnderoverscriptBox[\(\[Sum]\), \(m = 
  0\), \(n\)]\((Binomial[x + s, m] \(
\*UnderoverscriptBox[\(\[Sum]\), \(k = 0\), \(m\)]\((
\*SuperscriptBox[\((\(-1\))\), \(k - m\)] Binomial[m, k] Flow[k - s, 
      z])\)\))\)\)*)
a := 21
Flow2[x_, z_] := 
 FP + (Semi2[x, z] - FP) ((-1)^x + 1)/
    2 + (Semi1[x, z] - FP) ((-1)^(x + 1) + 1)/2
FL[x_, z_] := Nest[ArcCos, Flow2[x + a, z], a]
Plot[{Semi1[x, 1], Semi2[x, 1], Re[FL[x, 1]], Im[FL[x, 1]]}, {x, -5, 
  5}, AspectRatio -> Automatic, PlotRange -> 3]
Plot[{Re[FL[0.5, x]], Im[FL[0.5, x]]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]
Plot[{Re[FL[0.5, FL[0.5, x]]], Cos[x]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]

The above can be illustrated by the graphic:

Here upper semi-flow (flow of cos(cos z)) ) is blue, lower semi-flow is red, real part of the flow is yellow, imaginable part of the flow is green. All flows are taken as point z=1.

Here blue is the real part and red is the imaginary part.

We can verify that the half-iterate repeated twice $\Phi(1/2,\Phi(1/2,z))$ (blue) follows cosine (red) quite well at positive half-periods, and anywhere the cone is positive (that is, on the imaginary axis as well):

I think this coincodes with the answer by Gerald Edgar above. A modified function, iterated twice gives cosine in all real axis:

This is a true half-iterate of cosine, which works on the whole real axis, producing exactly cosine:

But as has been noted by Joel David Hamkins above, there is infinite number of such solutions, none of which work for the whole complex numbers.

This function can be considered though as the true solution on the complex plane if interpreted as a multi-valued function. To do this, take the function on the each interval and analytically extend it to the whole complex plane.

A mathematica notebook that produces the above is as follows:

$PlotTheme = None; 
f[x_, z_] := If[x >= 0, Nest[Cos, z, 2*x], Nest[ArcCos, z, -2*x]]
n := 30
s := 15
Ni[x_, z_] := 
 Sum[Binomial[x + 1, m]*
   Sum[(-1)^(k - m)*Binomial[m, k]*f[k - 1, z], {k, 0, m}], {m, 0, n}]
Semi2[x_, z_] := Ni[x/2, z]
Semi1[x_, z_] := ArcCos[Semi2[x + 1, z]]
FP := Evaluate[N[FixedPoint[Cos, 1.]]]
a := 21
Flow2[x_, z_] := 
 FP + (Semi2[x, z] - FP)*(((-1)^x + 1)/2) + (Semi1[x, z] - 
     FP)*(((-1)^(x + 1) + 1)/2)
FL[x_, z_] := Nest[ArcCos, Flow2[x + a, z], a]
Plot[{Semi1[x, 1], Semi2[x, 1], Re[FL[x, 1]], Im[FL[x, 1]]}, {x, -5, 
  5}, AspectRatio -> Automatic, PlotRange -> 3]
Plot[{Re[FL[0.5, x]], Im[FL[0.5, x]]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]
Plot[{Re[FL[0.5, FL[0.5, x]]], Cos[x]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]
HalfCos[z_] := 
 If[Im[z] == 0, Sign[Re[Cos[z]]]*FL[0.5, z], Sign[Re[z]]*FL[0.5, z]]
Plot[{Re[HalfCos[x]], Im[HalfCos[x]]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]
Plot[{Re[HalfCos[HalfCos[x]]], Cos[x]}, {x, -5, 5}, 
 AspectRatio -> Automatic, PlotRange -> 3]

We can verify that the half-iterate repeated twice $\Phi(1/2,\Phi(1/2,z))$ follows cosine quite well at least at positive half-periods: alt text http://storage4.static.itmages.ru/i/12/0529/h_1338260827_7686578_7b7eaac3d1.png

We can verify that the half-iterate repeated twice $\Phi(1/2,\Phi(1/2,z))$ (blue) follows cosine (red) quite well at least at positive half-periods: alt text http://storage4.static.itmages.ru/i/12/0529/h_1338260827_7686578_7b7eaac3d1.png

$$\phi_{1}(x,z)=\sum_{m=0}^n \binom{x/2+1}{m} \sum_{k=0}^m (-1)^{k-m} \binom{m}{k} \phi_{1/2}(k-1,z)$$

$$\phi_{1}(x,z)=\sum_{m=0}^\infty \binom{x/2+1}{m} \sum_{k=0}^m (-1)^{k-m} \binom{m}{k} \phi_{1/2}(k-1,z)$$