半圖埃系統的不可判定性(undecidability ofsemi-Thue system)半圖埃系統字問題的不可判定特性.半圖埃系統的判定問題是指:是否存在一個能行的算法。
半圖埃系統的不可判定性(undecidability ofsemi-Thue system)半圖埃系統字問題的不可判定特性.半圖埃系統的判定問題是指:是否存在一個能行的算法，使得對任何半圖埃系統S及S的任意兩個字W，，WZ，該算法可以判定
Wl=>W:
是否成立.由於這個問題是對所有的半圖埃系統而言的，因此也稱為一般半圖埃系統的字問題.事實上，可以證明對於任何圖靈機，可以構造一個半圖埃系統來模擬圖靈機的計算.因此，可以把停機問題對應到一個半圖埃系統的字問題.故由停機問題的不可判定性可以知道(一般的)，半圖埃系統的字問題是不可判定的.特別地，對某個具體的半圖埃系統，也有相應的特殊半圖埃系統的字問題，它們的判定性依賴於所給的半圖埃系統.但確實存在半圖埃系統，使該系統相應的字問題是不可判定的.
Wl=>W:
是否成立.由於這個問題是對所有的半圖埃系統而言的，因此也稱為一般半圖埃系統的字問題.事實上，可以證明對於任何圖靈機，可以構造一個半圖埃系統來模擬圖靈機的計算.因此，可以把停機問題對應到一個半圖埃系統的字問題.故由停機問題的不可判定性可以知道(一般的)，半圖埃系統的字問題是不可判定的.特別地，對某個具體的半圖埃系統，也有相應的特殊半圖埃系統的字問題，它們的判定性依賴於所給的半圖埃系統.但確實存在半圖埃系統，使該系統相應的字問題是不可判定的.
