0
I는 다음과 같습니다 튜링 기계 속성이 상상? 또는 더 일반적으로 이런 종류의 것을 증명할 수있는 좋은 방법이 있습니까?어떻게 튜링 기계의 속성은 간단하다 증명하기 위해
A
답변
3
힌트 : "이상한"사본과 "짝수"사본 인 상태의 사본을 2 개 만들고, 전환시에 앞뒤로 전환하여 TM을 항상 홀수 개의 단계 내에서 정지시킬 수 있습니다. 나오다. 일단이 작업을 마쳤 으면 짝수 단계로 중단되지 않도록이 기계를 어떻게 수정 하시겠습니까? 이 구조가 임의의 TM에 대해 작동한다고 가정 할 때 위의 특성이 왜 사소한 지 알 수 있습니까?
희망이 도움이됩니다.
관련 문제
- 1. 튜링 기계의 정지가 정확히 무엇입니까?
- 2. 반복 문자열에 대한 튜링 기계의 시간 복잡도
- 3. 어떤 튜링 기계 확장이 기계의 파워를 확장합니까?
- 4. 2 스택 PDA와 멀티 테루 튜링 기계의 장점
- 5. 튜링 기계를 어떻게 시뮬레이트 할 수 있습니까?
- 6. 튜링 기계 명령 표
- 7. 합계 증명하기
- 8. 비 결정적 튜링 기계
- 9. 보편적 인 튜링 기계 예
- 10. 자동 속성은 어떻게 컴파일됩니까?
- 11. 특정 언어 증명하기 일반
- 12. 기계가 튜링 기계와 동일한 지 확인하는 방법
- 13. 비 결정적 튜링 기계가있는 상황에 맞는 언어
- 14. 무언가를 증명하기 위해 NP 하드, 왜 NP 완성에서 그것을 줄일 필요가 있습니까? 위키
- 15. 튜링 기계
- 16. SQL 쿼리 (아마도 간단하다)
- 17. 언어 속성 증명하기
- 18. Request.RawUrl 속성은 어떻게 변경합니까?
- 19. 왜 P = NP는 다항식 시간에서 풀 수있는 튜링 기계의 정지를 암시하지 않습니까?
- 20. 튜링 기계가 결정자인지 어떻게 알 수 있습니까?
- 21. 혼동이 코드는 간단하다
- 22. 내가이 보조 정리를 증명하기 위해 노력하고있어 기능 곱셈
- 23. 튜링 기계와 아이디어가 떠오른다
- 24. AlwaysEnableSilent 속성은 무엇을 위해 사용됩니까?
- 25. 튜링 기계 번호가
- 26. 튜링 머신을 어떻게 풀 수 있습니까? anbncn/n> = 1일까요?
- 27. Group_Concat을 사용하여 주문하기 까다로운 증명하기
- 28. f (f bool) = bool 증명하기
- 29. Environment.CommandLine 속성은 어떻게 수정합니까?
- 30. DataGridViewCell.Datagridview 속성은 어떻게 설정됩니까?
좋은 질문이지만 [so]에 대한 프로그래밍 질문이 아닙니다. 아마도 [cs.se]에 대해 더 잘 질문 할 것입니다. –