/sci/ - Science & Math » Thread #12603383

79KiB, 773x491, turingmachine.png

View Same Google iqdb SauceNAO

Anonymous Wed 20 Jan 03:27:09 2021 No.12603383 View Reply Original Report

Quoted By: >>12604085

How can I tell if a turing machine accepts some input? I have this machine here (pic related). And I have the following input: abcab

I believe the machine will proceed to state q1, then proceed to q2, then proceed to q3, but then what happens at q3? Will the machine stop or return back to q0?

Anonymous

Anonymous Wed 20 Jan 2021 03:46:46 No.12603441 Report

Quoted By: >>12603464

what does (a,X,R) mean

Anonymous

Anonymous Wed 20 Jan 2021 03:53:29 No.12603459 Report

Quoted By:

A Turing machine accepts if it ends in an accept state after reading the string.

The idea is that you have a tape that characters are read from and written to. Because the input is abcab that’s what you start with on the tape.

I’ll go out on a limb and assume the tuples mean (read character, write character, move tape head).

So the machine looks like: (I use aHb to mean the read head is at the character a. So if we have XabHc or something the read head is at b)

aHbcab q0
XbHcab q1
XYcHab q2
XYHZab q3 (note head moves to left)
XHYZab q3
XYHZab q0 (had to move back to q0 cause we saw X)
XYZHab q4
XYZaHb q4

???? Now there’s no transition out of q4 on A. So assuming I didn’t fuck up, the string is not accepted. However, I probably fucked up, as I did this on an iPhone in front of a TV.

Do you have the sipser book ???

Anonymous

Anonymous Wed 20 Jan 2021 03:55:03 No.12603464 Report

Quoted By: >>12603485

>>12603441
Not op but I’m interpreting it to mean: when you see an a on the tape, write an X and move the read head to the right

Anonymous

Anonymous Wed 20 Jan 2021 04:00:41 No.12603485 Report

Quoted By: >>12603498

>>12603464
q0: a turns into X
q1: does nothing to X, the end

Anonymous

Anonymous Wed 20 Jan 2021 04:03:45 No.12603498 Report

Quoted By: >>12604031

>>12603485
It starts in q0, reads the a and writes the X over it; then moves to q1 and moves the read head to the right. Now the read head is on b, so it can keep reading and stepping through the states

Anonymous

Anonymous Wed 20 Jan 2021 07:13:22 No.12604031 Report

Quoted By:

>>12603498
ah ok
thanks

Anonymous

Anonymous Wed 20 Jan 2021 07:28:47 No.12604085 Report

Quoted By:

>>12603383
>turing machine state diagram for a^n b^n c^n
>input is not a^n b^n c^n

Of course it isn't accepted.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches