Re: зачем программисту машина Тьюринга
От: mefrill Россия  
Дата: 12.12.06 06:27
Оценка: 45 (9) +8 -1 :)
Здравствуйте, CRLF, Вы писали:

CRL>Hi all,

CRL>подскажите зачем программисту машины Тюринга ?
CRL>Сам учился на заочном и нас эта тема миновала.
CRL>А теперь вот от любопытства заглянул в учебник, чтобы получить общее
CRL>представление.
CRL>Представление получил, а теперь мучает вопрос практического применения
CRL>сабжа.

Машина Тьюринга — это абстрактная математическая модель понятия алгоритма. Все вроде бы знают что такое алгоритм, но этого недостаточно для математика. Математику необходимо изучить границы применения этого понятия, какие процессы можно описать на языке алгоритмов, а какие нельзя. Чтобы это выяснить, приходится поступать как всегда, а именно: вводить математическую абстракцию, специальный математическо-строгий объект, который является абстракцией понятия алгоритма. Вот Тьюринг предложил такую абстракцию в виде машины, исполняющей простейшие команды. Такую же абстракцию, но еще более простую, предложил Пост. Наш математик Марков придумал другую модель — нормальный алгорифм Маркова. Есть и другие абстракции, например рекурсивные функции. Все эти абстракции описывают одно и тоже явление — алгоритм. Доказано, что они эквивалентны, т.е. одно определение влечет за собой другое и наоборот. Вопрос, который остается открытым: действительно ли эти модели описывают все из того, что мы считаем алгоритмом? В настоящее время примеров обратного не было найдено. Именно об этом и говорит тезис Черча, в смысле что описывают. В теории таким образом определенных алгоритмов четко выяснены границы применения данного понятия для описания явлений окружающей нас действительности, что собственно и было целью теории. Зачем это нужно программисту? В повседневной работе, конечно, вряд ли понадобится. Тем более, если программист и с алгоритмами то по особому счету не сталкивается, так формы программирует и все. В этом случае, наверное, и не нужно ничего такого изучать. Достаточно закончить техникум или профтехучилище и научится работе с командной строкой и клепанием формочек. Вон в Индии таки людей и образовывают, и ничего, живут же люди и деньги зарабатывают. Но для решения серьезных задач такое образование не подходит, необходим более широкий взгляд на проблему, знание методологии. Такое знание и понимание дается только одним: широким образованием. образование — это не тупое поглощение знаний, т.е. закончивший Университет тем только и отличается от закончившего Техникум, что "знает больше". Нет, образование — это прежде всего понимание взаимосвязей в казалось бы совсем не относящихся друг к другу явлениях, выработка умения видеть в казалось бы разных процессах одни и те же основания. Все это дается академическим образованием. И машина Тьюринга является частью такого образования. В общем, это из той же оперы зачем программисту иметь представление об истории философии или, например, о функциональном анализе.
Re: зачем программисту машина Тьюринга
От: Аноним  
Дата: 11.12.06 20:04
Оценка: 3 (2) +2
Здравствуйте, CRLF, Вы писали:

CRL>Hi all,

CRL>подскажите зачем программисту машины Тюринга ?

Вообще-то в теории aлгоритмов это изучают.
В ней, к примеру, дается определение "алгоритмически разрешимых"
и "алгоритмически неразрешимых" задач.
Один из примеров "алгоритмически неразрешимой" задачи — это
проблема "самоприменимости машины Тьюринга".
Теория aлгоритмов в целом и машина Тьюринга в частности — это
штука полезная для общего развития программиста.

Эх...
Помню как писал программу для вычисления exp(x) для машины Тьюринга.
Хорошая была тренировка для мозгов
Re[2]: зачем программисту машина Тьюринга
От: Mab Россия http://shade.msu.ru/~mab
Дата: 12.12.06 09:46
Оценка: 12 (2)
Здравствуйте, mefrill, Вы писали:

M>Машина Тьюринга — это абстрактная математическая модель понятия алгоритма.

+1
Добавлю еще только, что модель эта в матемкатике в первую очередь нужна тем разделам, где изуячается алгоримтическая сложность (разрешимость) без ограничения на временные ресурсы (теория рекурсии, колмогоровская сложность итп). Для algorithms design МТ не подходит в принципе, там нужно другие (более сложные) модели вроде pointer machine model и (более сильной) random access machine model. На них уже можно сранительно адекватно моделировать поведение современных CPU (оставим в стороне параллельные машины, для которых классы свои).
Re[3]: зачем программисту машина Тьюринга
От: Cyberax Марс  
Дата: 12.12.06 20:15
Оценка: -2
Mab wrote:
> Для algorithms design МТ не подходит в принципе, там
> нужно другие (более сложные) модели вроде pointer machine model и (более
> сильной) random access machine model.
Двойка.

Они обе эквивалентны МТ. То есть на машине Тьюринга можно эмулировать их
обоих.
Posted via RSDN NNTP Server 2.1 beta
Sapienti sat!
Re: зачем программисту машина Тьюринга
От: Аноним  
Дата: 11.12.06 15:22
Оценка: +1
Здравствуйте, CRLF, Вы писали:

CRL>Hi all,

CRL>подскажите зачем программисту машины Тюринга ?
CRL>Сам учился на заочном и нас эта тема миновала.
CRL>А теперь вот от любопытства заглянул в учебник, чтобы получить общее
CRL>представление.
CRL>Представление получил, а теперь мучает вопрос практического применения
CRL>сабжа.

Помню, у нас на экзамене по С++ были вопросы типа:
"Информация — это...", "Особенности первых советских ЭОМ....".
Re[4]: зачем программисту машина Тьюринга
От: raskin Россия  
Дата: 12.12.06 20:20
Оценка: +1
Cyberax wrote:
>> Для algorithms design МТ не подходит в принципе, там
>> нужно другие (более сложные) модели вроде pointer machine model и (более
>> сильной) random access machine model.
> Двойка.
>
> Они обе эквивалентны МТ. То есть на машине Тьюринга можно эмулировать их
> обоих.
Только для algorithm design возведение временной сложности в квадрат
просто так (при переходе от RAM к машине Тьюринга) — это не самое
удачное действие. Речь-то даже не о полиномиальной вычислимости вообще,
а о конкретных оценках на время работы.
Posted via RSDN NNTP Server 2.1 beta
Re[4]: зачем программисту машина Тьюринга
От: Mab Россия http://shade.msu.ru/~mab
Дата: 12.12.06 20:31
Оценка: +1
Здравствуйте, Cyberax, Вы писали:

C>Они обе эквивалентны МТ. То есть на машине Тьюринга можно эмулировать их

C>обоих.
Можно-то можно, да только асимптотика времени при этом возрастет как минимум квадратично. Скажем, распознать быстрее, чем за O(n^2) тот факт, что введенная строка -- палиндром, на однолетночной МТ нельзя. Слишком эта модель далека от того, что мы видим в аппаратуре.
зачем программисту машина Тьюринга
От: CRLF  
Дата: 11.12.06 15:10
Оценка:
Hi all,
подскажите зачем программисту машины Тюринга ?
Сам учился на заочном и нас эта тема миновала.
А теперь вот от любопытства заглянул в учебник, чтобы получить общее
представление.
Представление получил, а теперь мучает вопрос практического применения
сабжа.
Posted via RSDN NNTP Server 2.0
Re[2]: зачем программисту машина Тьюринга
От: oziro Нигерия  
Дата: 11.12.06 21:45
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Эх...

А>Помню как писал программу для вычисления exp(x) для машины Тьюринга.
А>Хорошая была тренировка для мозгов

Да, мозги еще как тренирует. Я писал на машине Тьюринга и на алгорифмах Маркова сложение и умножение целых чисел — ох, и задачка была для меня. Зато после этого сознание, что ли, перевернулось немного, особенно после алгорифмов, стал мысли более алгоритмически, чем языковыми конструкциями. ИМХО, обязательно надо въехать и попробовать написать хотябы самое простое.
Re: зачем программисту машина Тьюринга
От: DerBober США  
Дата: 11.12.06 22:19
Оценка:
Здравствуйте, CRLF, Вы писали:

CRL>Hi all,

CRL>подскажите зачем программисту машины Тюринга ?
CRL>Сам учился на заочном и нас эта тема миновала.
CRL>А теперь вот от любопытства заглянул в учебник, чтобы получить общее
CRL>представление.
CRL>Представление получил, а теперь мучает вопрос практического применения
CRL>сабжа.

Например тебе нужно решить задачу. Решаешь, программируешь, проверяешь и все отлично.
Как быть если не получается решить задачу? Начинает мучать вопрос "имеет ли задача решение?".
Надо доказывать ее алгоритмическую неразрешимость. Тут то и нужны формальные модели типа Машин Тюринга, автоматов и алгорифмов Маркова и т.д.
Re[2]: зачем программисту машина Тьюринга
От: CRLF  
Дата: 12.12.06 09:37
Оценка:
>Зачем это нужно программисту? В повседневной работе, конечно, вряд ли
>понадобится. Тем более, если
>программист и с алгоритмами то по особому счету не сталкивается, так формы
>программирует и все. В этом случае,
>наверное, и не нужно ничего такого изучать. Достаточно закончить техникум
>или профтехучилище и научится
>работе с командной строкой и клепанием формочек. Вон в Индии таки людей и
>образовывают, и ничего, живут же
>люди и деньги зарабатывают. Но для решения серьезных задач такое
>образование не подходит, необходим более
>широкий взгляд на проблему, знание методологии. Такое знание и понимание
>дается только одним: широким
>образованием. образование — это не тупое поглощение знаний, т.е.
>закончивший Университет тем только и
>отличается от закончившего Техникум, что "знает больше". Нет, образование —
>это прежде всего понимание
>взаимосвязей в казалось бы совсем не относящихся друг к другу явлениях,
>выработка умения видеть в казалось бы
>разных процессах одни и те же основания. Все это дается академическим
>образованием. И машина Тьюринга
>является частью такого образования. В общем, это из той же оперы зачем
>программисту иметь представление об
>истории философии или, например, о функциональном анализе.
Только не надо флейм разводить.
Я, кажется, не утверждал, что программисту это не нужно, а спрашивал
"зачем", поскольку сам в силу ущербности своего образования (кстати
формально университетского) этого не вижу.
А что касается образования, не знаю как там в Индии, Москве и Ленинграде, но
в нашей глубинке образование как раз и опускается на уровень клепания
формочек, а то и ниже.
Posted via RSDN NNTP Server 2.0
Re[3]: зачем программисту машина Тьюринга
От: mefrill Россия  
Дата: 12.12.06 09:43
Оценка:
Здравствуйте, CRLF, Вы писали:

CRL>Только не надо флейм разводить.

CRL>Я, кажется, не утверждал, что программисту это не нужно, а спрашивал
CRL>"зачем", поскольку сам в силу ущербности своего образования (кстати
CRL>формально университетского) этого не вижу.
CRL>А что касается образования, не знаю как там в Индии, Москве и Ленинграде, но
CRL>в нашей глубинке образование как раз и опускается на уровень клепания
CRL>формочек, а то и ниже.

Ты спросил зачем, я как мне кажется, ответил. Чем мой ответ не удовлетворил то? Если увидел в моем ответе желание унизить или еще как-то оскорбить, то уверяю: ничего такого не было и нет. Вопрос ведь на самом деле сводится к тому, в чем состоит разница между высшим и средним специальным образованием. А про уровень образования так здесь об этом много было написано. Но это совсем другая тема и к тому, в чем состоит цель изучения машины Тьюринга, имеет мало отношения.
Re[3]: зачем программисту машина Тьюринга
От: Аноним  
Дата: 12.12.06 10:47
Оценка:
Здравствуйте, CRLF, Вы писали:

CRL>Только не надо флейм разводить.


Ну если ты что-то на свой счет перенял, то это твои личные проблемы.
А по сути так и есть, как описал mefrill
Для клепания форм машина Тьюринга и теория алгоритмов не нужна.

Кстати, одна из проблем подготовки программистов в России в том,
что их в основном готовят в универах...
Не очень велик выбор у тех кто считает, что ему нужны только конкретные практические знания,
чтобы как можно быстрей пойти работать,.
Часто выбор просто делается в сторону "ну его нафиг, это образование"...
Re[4]: зачем программисту машина Тьюринга
От: Аноним  
Дата: 12.12.06 12:07
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, CRLF, Вы писали:


CRL>>Только не надо флейм разводить.


А>Ну если ты что-то на свой счет перенял, то это твои личные проблемы.

А>А по сути так и есть, как описал mefrill
А>Для клепания форм машина Тьюринга и теория алгоритмов не нужна.

А>Кстати, одна из проблем подготовки программистов в России в том,

А>что их в основном готовят в универах...
А>Не очень велик выбор у тех кто считает, что ему нужны только конкретные практические знания,
А>чтобы как можно быстрей пойти работать,.
А>Часто выбор просто делается в сторону "ну его нафиг, это образование"...

Учась на факультете информатики в универе из программирования я видел лишь Borland C++ 3.1 и клепание формочек на Visual Basic, поэтому в конце второго курса забил на "учебу" и ушел на работу, чтобы получить реальные знания и опыт. Немного завидую тем, кому приходилось обучаться у толковых преподавателей, так как мой диплом вызывает у меня только мерзкие ощущения.
Re[3]: зачем программисту машина Тьюринга
От: LaptevVV Россия  
Дата: 12.12.06 12:16
Оценка:
Здравствуйте, CRLF, Вы писали:

CRL>А что касается образования, не знаю как там в Индии, Москве и Ленинграде, но

CRL>в нашей глубинке образование как раз и опускается на уровень клепания
CRL>формочек, а то и ниже.
А в нашей глубинке — не опускается...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[4]: зачем программисту машина Тьюринга
От: CRLF  
Дата: 12.12.06 13:15
Оценка:
CRL>А что касается образования, не знаю как там в Индии, Москве и
Ленинграде, но
CRL>в нашей глубинке образование как раз и опускается на уровень клепания
CRL>формочек, а то и ниже.
>А в нашей глубинке — не опускается...
Завидую вам.
Где проживаете ?
Posted via RSDN NNTP Server 2.0
Re[5]: зачем программисту машина Тьюринга
От: bkat  
Дата: 12.12.06 13:52
Оценка:
Здравствуйте, CRLF, Вы писали:

CRL>Где проживаете ?


У него в профайле написано:
"Специализация — преподаватель
Откуда — Астрахань"
Думаю, что это правда

А вообще, глубинка — это понятие для России бесполезное и вредное.
Города в Сибири и на Дальнем Востоке слишком далеки
от Москвы и Питера, чтобы считаться провинцией
Так что ссылаться на провинциальность и удаленность — это плохая, на мой взгляд, отговорка.
Re[6]: зачем программисту машина Тьюринга
От: LaptevVV Россия  
Дата: 12.12.06 14:40
Оценка:
Здравствуйте, bkat, Вы писали:

B>Здравствуйте, CRLF, Вы писали:


CRL>>Где проживаете ?


B>У него в профайле написано:

B>"Специализация — преподаватель
B> Откуда — Астрахань"
B>Думаю, что это правда

Это правда...
Особенно приятно, когда в городских объявлениях о поиске специалиста по информационным технологиям ставят условие: ТОЛЬКО АГТУ — то есть мы, наша кафедра...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[7]: зачем программисту машина Тьюринга
От: CRLF  
Дата: 13.12.06 05:52
Оценка:
B>У него в профайле написано:
B>"Специализация — преподаватель
B> Откуда — Астрахань"
B>Думаю, что это правда
Ну какая же Астрахань глубинка ?!
Там поди часовой пояс-то даже московский
Posted via RSDN NNTP Server 2.0
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.