튜링 기계 정지 문제

기계 튜링과 문제 해결에 관한 질문이 있습니다.튜링 기계 정지 문제

우리 ATM을 = 및 {M 튜링 기계 및 w이다 (M, w)의 입력} 있다고 가정
HALTtm = {(M, W) M은 튜링 기계이고는 입력 w와 정지 } 내가 HALTtm < = m 현금 지급기

내가 몇 가지 방법을 시도했지만 나는 그들이 지금까지 용액으로부터라고 생각 증명하려는

. 누구나 단서를 줄 수 있습니까 ??

2010-03-24 iva123

이 질문은 다가오는 [컴퓨터 과학 스택 교환] (http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2)에 적합했을 것입니다. 따라서, 이와 같은 질문을 할 장소가 있으면이 제안서를 벗겨 내십시오. – Raphael

정확하게 무엇을 의미합니까? '\ leq_m'으로 읽었지 만 어떻게 정의 되었는가? – Raphael

음, HALTtm의 모든 (M, w)에 대해 (M, w)가 Atm이어야 함을 관찰하십시오. 그렇다면 Atm의 멤버이지만 멈추지 않는 HALTtm의 일부 (M ', w')가 있음을 보여줍니다.

출처

2010-03-24 18:55:56 Fred

두 번째 단계는 필요하지 않습니다. 그는 "<="를 사용했는데 아마도 "*와 같거나 * 같음"을 의미하기위한 것입니다. – sepp2k

<= m은 [many-one reduction] (http://en.wikipedia.org/wiki/Manyone_reduction)의 존재를 의미한다고 생각합니다. 이 경우 OP가 증명하려고하는 것은 사실이 아닙니다. – Prateek

다음 언어 각각에 대해 해당 언어를 사용할 수있는 튜링 머신의 전환 다이어그램을 그립니다.

{aibj | i≠j}

출처

2011-05-06 03:51:25 rabea

< = m은 무엇인가? "many-one reduces to"을 말하는 것 같습니까? 이 경우, 당신을 위해 무엇을 요구하는지 모든 문자열 X의

가 X 경우에만 F (x)의 경우 HALTtm 속한 ATM 속한 총 계산 가능한 함수 f 등이다

그러한 f가 존재하면 정지 문제를 결정할 수 있습니다. x를 주어 f (x)를 계산하고 f (x)가 Atm에 속하는지 확인합니다 (Atm은 쉽게 재귀/결정 가능합니다). 그러나 정지 문제는 결정할 수 없으므로 그러한 f는 존재할 수 없다. 그래서 HALTtm 은 많은 사람이 Atm으로 감소하지 않습니다.

출처

2011-12-06 14:00:14 Prateek

튜링 기계 정지 문제

답변

관련 문제