2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 неразрешимость по Тьюрингу
Сообщение18.12.2010, 21:00 
Аватара пользователя
Доказать неразрешимость по Тьюрингу проблемы эквивалентности.

(Оффтоп)

Т.е. то, что язык E={$<T_1,T_2>|L(T_1)=L(T_2)$} -не разрешим, где $<T_1>$ главный код машины Тьюринга $T_1,<T_2>$ главный код машины Тьюринга $T_2, L(T_1)$ язык, распознаваемый машиной Тьюринга $T_1,L(T_2)$ язык, распознаваемый машиной Тьюринга $T_2$.

Пытался найти доказательство в интернете, там сводят это доказательство к неразрешимости проблемы самоприменимости, но я не понимаю как. А самому доказать не удаётся.

 
 
 
 Re: неразрешимость по Тьюрингу
Сообщение20.12.2010, 00:43 
Аватара пользователя
Уже придумал как доказать это. Тему можно удалять)

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group