���ޡ��ȥե����Ѥ�ɽ���Ǹ���

Turing machine

�����ԥ塼��

Turing Machine

���塼���󤰤ޤ���

����

�ѹ������ؼ������󡦥��塼�����������۵����Ȥ��ƹͰƤ�����

���塼���󥰥ޥ�����1�ܤΥơ��פȡ����Υơ��׾��ε������ɤ߽񤭤��뤿���Υإåɤ����Ļ��Ĥ����β��۵����Ǥ��롣���塼���������ޥ����ˤ�ͭ�¸ĤΡ־��֡פ����äơ��ƻ����Ǥ��Τ������줫���Ĥξ��֤��Ȥ뤳�Ȥ��Ǥ��롣

����Ū�˽񤱤аʲ����ͤˤʤ롣

  • TM =(Q,��Sigma,��Gamma,��delta,q_0,H)
Q
���֤ν���
��Sigma
�������֤Υơ��פ˽񤫤��Ƥ��륢���ե��٥å�
��Gamma
�ơ��פ˽񤫤��륢���ե��٥å�,��Sigma ��subseteq ��Gamma
��delta
�����ؿ�(Q��times ��Gamma ��rightarrow Q��times ��Gamma ��times D)
D=��{L,S,R��}
�إåɤΰ�ư����
q_0
���Ͼ���,q_0 ��in Q
H
��������,H ��subseteq Q

�׻���ǽ�Ȥ������Ǥ�n�ơ���Turing Machine,��ΨŪTuring Machine,��������Turing Machine,�̻���Turing Machine��Ʊ�ͤ�ǽ�Ϥ����ġ����Ϥ��Ф����׻����ֵڤӻ��Ѥ����ơ��פ�Ĺ�����ˤϰ㤤�������ˡ�

���¤������ԥ塼�������塼���󥰥ޥ����Υ��֥��åȤȤ����롣�����ԥ塼���Υ����꤬ͭ�¤Ǥ����Τˤ����������塼���󥰥ޥ����Υơ���Ĺ�ˤ����¤��ʤ�����ǰŪ�ˤϤۤ������Ȥ����롣