הכרעת שפות

הגדרה: יהי   S1 א"ב כך  ש: 1S Ï #   ותהיL Í S1   שפה.

תהי  S,h),(Q,S,d M=  מכונת טיורינג. נאמר כי M  מכריעה את L  את לכל wÎS1*  מתקיים:

  ( s , # w #)|-----( h , # 1 # )                                    אם  wÎ L         

                                    ) # o  ( s , # w #)|-----( h , # אם   wÏ L     

כלומר, אם מילה נמצאת בשפה, המכונה תחזיר 1 , אחרת היא תחזיר 0.