Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

# Tyrrell_McAllister comments on No coinductive datatype of integers - Less Wrong

4 04 May 2011 04:37PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

## Comments (137)

Sort By: Best

You are viewing a single comment's thread. Show more comments above.

Comment author: 05 May 2011 05:06:45PM *  0 points [-]

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."

Comment author: 05 May 2011 06:29:22PM 0 points [-]

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.

Comment author: 05 May 2011 06:37:36PM 0 points [-]

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 . . .)

Comment author: 06 May 2011 07:49:08AM 0 points [-]

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.