From kragen@dnaco.net Thu Aug 27 14:30:09 1998 Date: Thu, 27 Aug 1998 14:30:07 -0400 (EDT) From: Kragen To: hugi-compo@makelist.com Subject: Re: [hugi-compo] SV: Turing machines In-Reply-To: <003601bdd1d9$7edc09e0$b16b3ac3@af004957> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Keywords: X-UID: 1517 Status: O X-Status: On Thu, 27 Aug 1998, Tobbe wrote: > Kragen wrote among else: > >It doesn't explain the mathematical insides (how to build one), just > >how it relates to the rest of the world. I can describe that, too, if > >you want. > > That would be kinda nice of you, this is starting to sound very interesting. OK. A Turing machine is a sort of a tape reader. It has a read-write head that moves along a tape, reading and writing symbols on it. The tape is infinitely long, but it has a beginning. It's fully specified by the following: 1. The alphabet of possible symbols that can appear on the tape. 2. The set of possible states the read-write head can be in. 3. The initial state the read-write head is in. 4. A particular state (or set of states) called "halting states". 5. A transition function that maps pairs (osymbol, ostate) into triples (nsymbol, nstate, motion), where 'motion' is one of left, right, or stationary. Here's how it works: a- We start with the read-write head being in the initial state (3) and positioned at the beginning of the tape, which has some kind of input written on it. b- Each "clock cycle", we look at the symbol at the read-write head's current position on the tape and the current state of the read-write head. c- We use function (5) and get a triple (nsymbol, nstate, motion). d- We change the symbol on the tape at the current position to 'nsymbol'. e- We change the state of the read-write head to 'nstate'. f- If 'motion' is "left", we move the read-write head one space to the left. (If that means moving off the tape, well, you've crashed the machine.) If 'motion' is "right", we move the read-write head one space to the right. If 'motion' is "stationary", we leave the read-write head in its current place. g- If the state is the halting state (4) (or one of the halting states, if you're doing it that way) then we stop, and the current content of the tape is the output; otherwise, we go back to step 'b' (starting the next "clock cycle"). Each space on the tape holds exactly one symbol, in case that's not clear. > >(BTW: the two-line C program I posted a few days ago was a Turing > >machine.) > > you mean the: > [code snip] > /* ./executable 4 ' }"!{ "} #}123123123123#!{!X|!"|!#|# {!X| #}##{' '""""" !' */ > int n,p=0,s=32;char*pt;main(int c,char**v){n=atol(v[1]);while(s!=33){pt=v[2]+3*(n*(s-32)+v[3][p]-32);s=pt[0];v[3][p]=pt[1];p+=pt[2]-'|';}puts(v[3]);} > [code ends] > stuff?? Right. > If that was a turing machine could you pleas deobfuscate it? just so > I that aint a C(++?) hacker could at least be near to understand what > it does. OK, here it is. It might have typos or brain-farts in it. Let me know if it does. int number_of_tape_symbols, position_on_tape=0, state=' '; char *pointer_to_transition; int main(int argc,char**argv) { /* first argument is number of different symbols that can appear * on the tape */ number_of_tape_symbols=atol(argv[1]); /* Each state is represented by a character. The state ' ' is the * initial state; the state '!' is the halting state. */ while(state != '!') { /* argv[2], the second command-line argument, * is the transition function. Here we index * within it, using the current state and the current * tape symbol, to find the transition. (This is step * (c) above.) * Each transition is represented by three characters: * one to specify the new state, one to specify the * new tape symbol, and one to specify the motion, in that * order. All the transitions for the first state ' ' are * written first -- first the one for the first tape symbol * ' ', then the one for the second tape symbol '!', etc., * in ASCII order, starting from ' '. Then, after the * last tape symbol's transition has been written, the * transitions for the second state '!' start, and are written * in the same order. Since '!' is the halting state, these * transitions are actually irrelevant, since we'll never * look at them. * Anyway, so the offset is three (the number of characters * in each transition) times the number of transitions * written before the transition we're looking for. That * number can be computed as the number of states all of * whose transitions are written before the state whose * transitions we're looking for, multiplied by the number * of transitions written for each state, plus the number * of transitions for other tape symbols but the same state * written before the particular transition we're looking for. * * Oh, by the way, argv[3] is the tape, and so * argv[3][positon_on_tape] is the symbol at the current * position on the tape. */ pointer_to_transition = argv[2] + 3*(number_of_tape_symbols*(state-' ') + argv[3][position_on_tape]-' '); /* * so we set state to nstate from the transition function */ state=pointer_to_transition[0]; /* then we write nsymbol */ argv[3][position_on_tape]=pointer_to_transition[1]; /* then we move. the "left", "right", and "stationary" * motions are encoded as '{', '|', and '}' respectively, * that is, '|' - 1, '|' + 0, and '|' + 1. So we subtract * '|' from the appropriate character in the transition * function string to give us -1, 0, or +1, then add it * to the position_on_tape. */ position_on_tape += pointer_to_transition[2]-'|'; } /* now we output the tape. */ puts(argv[3]); } It has the theoretical problem that its tape is not infinite. Let me know if any of this is unclear; I'll be happy to explain further. Kragen -- Kragen Sitaker We are forming cells within a global brain and we are excited that we might start to think collectively. What becomes of us still hangs crucially on how we think individually. -- Tim Berners-Lee, inventor of the Web