チューリングの神託機械自体はすでに定義されているものなので、
どうせ計算しないんだから複雑度がわかればよくて実装はなんでもよくて、
wikipediaのoracle machineにはvan Melkebeekの実装が書かれている