Vs K unf vasvavgryl znal inyvq fhssvkrf, ng yrnfg bar bs K0 be K1 zhfg unir vasvavgryl znal inyvq fhssvkrf. Fb yrg k_{x+1} = 0 vs k_1 … k_x 0 unf vasvavgryl znal inyvq fhssvkrf, naq 1 bgurejvfr; gura k_1 gb k_x unf vasvavgryl znal inyvq fhssvkrf sbe nal x.
Ner gurer frgf bs inyvq fgevatf fhpu gung ab Ghevat znpuvar N pbhyq vzcyrzrag guvf “nggnpx” ba gur bevtvany znpuvar G? Gung vf, qbrf gurer rkvfg n G fhpu gung, rira vs N unf npprff gb G’f fbhepr pbqr, N pnaabg gryy pbapyhfviryl juvpu bs K0 be K1 unf vasvavgryl znal inyvq fhssvkrf? Vs fb, pna lbh npghnyyl pbafgehpg n G gung cebinoyl unf guvf cebcregl?
ETA: Looks like cousin_it says that the answer to my existence question is “Yes.”
The “original Turing machine” decides whether a prefix is valid? Then yes definitely; bear in mind Rice’s theorem, which basically says that no non-trivial property of a Turing machine is computable.
The “original Turing machine” decides whether a prefix is valid?
If I understand you, yes. By the “original Turing machine”, I meant the machine T that putatively can interpret an input string as an integer or, alternatively, reject the input string as not corresponding to any integer.
So, can we actually construct such a machine that is provably immune to the “attack” in your proof, in the sense that no Turing machine could implement the attack? Or are you saying that Rice’s theorem (with which I will have to acquaint myself) says that pretty much any Turing machine T that maps strings to integers will fit the bill? (Though, the one in cousin_it’s OP doesn’t . . .)
Hmm. So T is an acceptor, A is an attacker. A(T) is an infinite sequence of symbols produced after examining T’s source code, and T(A(T)) = ⊥ means T never rejects the sequence. Then what I was asserting is ¬∃A:∀T:T(A(T)) = ⊥. What you’re asking now is whether ∀T:∃A:T(A(T)) = ⊥ and I can’t immediately work out the answer.
Ner gurer frgf bs inyvq fgevatf fhpu gung ab Ghevat znpuvar N pbhyq vzcyrzrag guvf “nggnpx” ba gur bevtvany znpuvar G? Gung vf, qbrf gurer rkvfg n G fhpu gung, rira vs N unf npprff gb G’f fbhepr pbqr, N pnaabg gryy pbapyhfviryl juvpu bs K0 be K1 unf vasvavgryl znal inyvq fhssvkrf? Vs fb, pna lbh npghnyyl pbafgehpg n G gung cebinoyl unf guvf cebcregl?
ETA: Looks like cousin_it says that the answer to my existence question is “Yes.”
The “original Turing machine” decides whether a prefix is valid? Then yes definitely; bear in mind Rice’s theorem, which basically says that no non-trivial property of a Turing machine is computable.
If I understand you, yes. By the “original Turing machine”, I meant the machine T that putatively can interpret an input string as an integer or, alternatively, reject the input string as not corresponding to any integer.
So, can we actually construct such a machine that is provably immune to the “attack” in your proof, in the sense that no Turing machine could implement the attack? Or are you saying that Rice’s theorem (with which I will have to acquaint myself) says that pretty much any Turing machine T that maps strings to integers will fit the bill? (Though, the one in cousin_it’s OP doesn’t . . .)
Hmm. So T is an acceptor, A is an attacker. A(T) is an infinite sequence of symbols produced after examining T’s source code, and T(A(T)) = ⊥ means T never rejects the sequence. Then what I was asserting is ¬∃A:∀T:T(A(T)) = ⊥. What you’re asking now is whether ∀T:∃A:T(A(T)) = ⊥ and I can’t immediately work out the answer.