[일반] 튜링머신에서 두 상태가 isomorphic한지 확인하는 방법

[익명(211.222)]

적어도, 읽은값에 대한 동작(쓸 값, 이동할 방향)이 같고 전이할 상태가 isomorphic하면 두 상태는 isomorphic하다.

만약 읽은값에 대한 동작이 다르다면 두 상태는 isomorphic할 수 없는가?

[익명(211.222)]

튜링머신이 임의의 입력에 대해 가지는 상태전이series상에서 어떤 상태 a가 적용된 phase를 상태 b로 대체하면 다른 series가 발생함. 임의의 입력에서 임의위치의 a를 대체하더라도 정지시 테이프의 모습과 헤드위치가 항상 동일하다면 둘은 isomorphic하다고 할 수 있을 것이다. 상태 b의 a대체 가능성에 대한 검사는 불필요할 것 같고, 아무리 a와 b를 헷갈려서 얼마나 많이 어떻게 잘못 적용하더라도 항상 결과가 같을 것 같다. 그리고 동작표 상에서 얘기하자면, 이건 아마 a를가지는 위치들 중 임의의일부를 b로 대체하더라도 임의의 입력에 대한 정지결과가 항상 동일한 것과 동치일거고, a를가지는 모든위치를 b로 대체하더라도 임의의 입력에 대한 정지결과가 항상 동일한 것과 동치일거같다.

[익명(211.222)]

처음부분 좀 잘못된듯. a를 한번 대체할 경우엔 결과가 같지만 a를 여러번 대체할경우엔 결과가 달라지는 경우가 없음을 보장못할거같다

[익명(211.222)]

isomorphic에 대한 가장 명쾌하고 간단한 정의는, 동작표상에서 a라는 상태에서의 동작을 정의하는 row들을 없애버리고, a라는 상태로 전이하는 부분들을 모두 b라는 상태로 전이하도록 수정한, 그렇게 간소화된 새로운 동작표가 기존의 동작표와 동일한 (입력 -> 결과) 를 낳는다면 isomorphic하다고 하면 될 것 같다. 결과 도달까지의 과정이 얼마나 복잡한지는 신경쓰지 않는다

[익명(211.222)]

정지하는입력을 정지하지않게하거나, 정지하지않는입력을 정지하게하는 경우가 존재한다면 그건 isomorphic하지 않다. 그런데 만약 정지하지않는 입력을 다른방식으로 정지하지않게 한다면 그땐아마 두 동작표 중 어떤 하나에서 일어나는 테이프의 변화가 다른 동작표에서 일어나는 테이프 변화를 오프셋해서 겹쳐질 수 있는지를 봐야할듯