2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 неразрешимость по Тьюрингу
Сообщение18.12.2010, 21:00 
Аватара пользователя


27/04/10
71
Нижний Новгород
Доказать неразрешимость по Тьюрингу проблемы эквивалентности.

(Оффтоп)

Т.е. то, что язык 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 
Аватара пользователя


27/04/10
71
Нижний Новгород
Уже придумал как доказать это. Тему можно удалять)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group