Discussion:
Что почитать соврменного по CS?
(слишком старое сообщение для ответа)
Alexander Zatvornitskiy
2006-01-10 22:25:53 UTC
Permalink
Привет RockMover!

10 января 2006 в 23:29, RockMover в своем письме к All писал:
R> Такой, оффтопичный вроде бы, вопрос. В вузах
R> из теории изучают в основном машину Тьюринга,
R> сети Петри и прочие примитивно-рекурсивные функции.
R> Между тем сейчас чуть ли не любому геймеру доступен комп более
R> мощный, чем машина Тьюринга.

R> Почти уверен, что есть соответствующая теория, и что здесь
R> есть люди, с ней знакомые. Посоветуйте, пожалуйста,
R> литературу, а также фамилии, ключевые слова для поиска.
Вообщем, для начала можно таки познакомиться с машиной Тьюринга:) А потом найти
такого геймера:)

R> WBR, RockMover
R> I am The Master of Flame...

Alexander, ***@bk.ru
Boris Sivko
2006-01-10 21:03:14 UTC
Permalink
Здравствуй, RockMover! Помнишь меня?

По данным контрразведки я узнал, что в Вторник Январь 10 2006 23:29,
RockMover писал All:

R> Такой, оффтопичный вроде бы, вопрос. В вузах
R> из теории изучают в основном машину Тьюринга,
R> сети Петри и прочие примитивно-рекурсивные функции.
R> Между тем сейчас чуть ли не любому геймеру доступен комп более
R> мощный, чем машина Тьюринга.

R> Почти уверен, что есть соответствующая теория, и что здесь
R> есть люди, с ней знакомые. Посоветуйте, пожалуйста,
R> литературу, а также фамилии, ключевые слова для поиска.

Теория соответствующая чему?

Счастливо, RockMover. Вспоминай обо мне...
... I'll be back...
RockMover
2006-01-11 16:12:31 UTC
Permalink
Привет!

[...]
Post by Alexander Zatvornitskiy
R> Почти уверен, что есть соответствующая теория, и что здесь
R> есть люди, с ней знакомые. Посоветуйте, пожалуйста,
R> литературу, а также фамилии, ключевые слова для поиска.
Теория соответствующая чему?
Вычислительным системам, более мощным, чем машина Тьюринга.
Интересно именно применительно к вычислительным системам
(и эхотагу), а не голая математика. Или считается, что для
практических задач моделирования на МТ достаточно?
Post by Alexander Zatvornitskiy
Счастливо, RockMover. Вспоминай обо мне...
... I'll be back...
WBR, RockMover
I am The Master of Flame...
Dmitry Grebeniuk
2006-01-11 13:32:56 UTC
Permalink
hi, RockMover

R> Между тем сейчас чуть ли не любому геймеру доступен комп более
R> мощный, чем машина Тьюринга.

Ленту бесконечной памяти не приделать. Машина Тьюринга концептуально мощнее
любого компьютера, который может только существовать.

R> Почти уверен, что есть соответствующая теория, и что здесь
R> есть люди, с ней знакомые. Посоветуйте, пожалуйста,
R> литературу, а также фамилии, ключевые слова для поиска.

Обычно теория, выводимая из работ Тьюринга, Черча и других, используется в
функциональном программировании, где я имел возможность ознакомиться с её
частью. Можно попробовать, но не думаю, что выяснится что-то действительно
стоящее. Хотя, может, родится уважение к функциональным языкам, что уже само
по себе отлично :)

bye
RockMover
2006-01-11 17:46:52 UTC
Permalink
Привет!

[...]
Post by Dmitry Grebeniuk
Ленту бесконечной памяти не приделать. Машина Тьюринга
концептуально мощнее любого компьютера, который может только
существовать.
Это еще почему? Я только знаю, что МТ мощнее любого компа,
эквивалентного МТ с конечной лентой. Но ведь бывают еще
аналоговые компы, может, еще какие...
Post by Dmitry Grebeniuk
R> Почти уверен, что есть соответствующая теория, и что здесь
R> есть люди, с ней знакомые. Посоветуйте, пожалуйста,
R> литературу, а также фамилии, ключевые слова для поиска.
Обычно теория, выводимая из работ Тьюринга, Черча и других,
используется в функциональном программировании, где я имел
возможность ознакомиться с её частью. Можно попробовать, но не
думаю, что выяснится что-то действительно стоящее. Хотя, может,
родится уважение к функциональным языкам, что уже само по себе
отлично :)
Спасибо, это я уже :-)
Уже успел ФЯ не только полюбить за красоту, но и невзлюбить
за то, что на практике ею ради эффективности приходится жертвовать,
как заглянешь куда-нибудь внутрь -- setq на setq сидит и progn'ом
погоняет. IO-монадами я, правда, так и не научился пользоваться.
Post by Dmitry Grebeniuk
bye
WBR, RockMover
I am The Master of Flame...
Serguey Zefirov
2006-01-12 00:13:19 UTC
Permalink
Post by Dmitry Grebeniuk
Ленту бесконечной памяти не приделать. Машина Тьюринга
концептуально мощнее любого компьютера, который может только
существовать.
R> Это еще почему? Я только знаю, что МТ мощнее любого компа,
R> эквивалентного МТ с конечной лентой. Hо ведь бывают еще
R> аналоговые компы, может, еще какие...

А они все эквивалентны в выразительной силе.

Или ты что-то другое имел в виду?
Post by Dmitry Grebeniuk
родится уважение к функциональным языкам, что уже само по себе
отлично :)
R> Спасибо, это я уже :-)
R> Уже успел ФЯ не только полюбить за красоту, но и невзлюбить
R> за то, что на практике ею ради эффективности приходится жертвовать,
R> как заглянешь куда-нибудь внутрь -- setq на setq сидит и progn'ом
R> погоняет. IO-монадами я, правда, так и не научился пользоваться.

Ага. ;)

Hачинай заново. ;)

Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
RockMover
2006-01-12 16:12:30 UTC
Permalink
Привет!
Post by Serguey Zefirov
Post by Dmitry Grebeniuk
Ленту бесконечной памяти не приделать. Машина Тьюринга
концептуально мощнее любого компьютера, который может только
существовать.
R> Это еще почему? Я только знаю, что МТ мощнее любого компа,
R> эквивалентного МТ с конечной лентой. Hо ведь бывают еще
R> аналоговые компы, может, еще какие...
А они все эквивалентны в выразительной силе.
А я в это не верю. Как можно доказать эквивалентность
аналогового компа и МТ? Рассматривают матмодель. Только
модель почему-то всегда выбирают изначально такую, которая
уже содержит эквивалентность.
Post by Serguey Zefirov
Или ты что-то другое имел в виду?
Я, когда написал о современных компах, имел в виду прежде
всего ГСЧ. Если мне докажут, что МТ+ГСЧ ~= МТ, буду
очень удивлен, но очень рад.
Post by Serguey Zefirov
Post by Dmitry Grebeniuk
родится уважение к функциональным языкам, что уже само по себе
отлично :)
R> Спасибо, это я уже :-)
R> Уже успел ФЯ не только полюбить за красоту, но и невзлюбить
R> за то, что на практике ею ради эффективности приходится жертвовать,
R> как заглянешь куда-нибудь внутрь -- setq на setq сидит и progn'ом
R> погоняет. IO-монадами я, правда, так и не научился пользоваться.
Ага. ;)
Hачинай заново. ;)
Может, посоветуешь чего почитать именно про монады?
(Не теорию категорий, а про практическое применение.)
Post by Serguey Zefirov
Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
WBR, RockMover
I am The Master of Flame...
Serguey Zefirov
2006-01-12 21:02:18 UTC
Permalink
Post by Serguey Zefirov
Post by Dmitry Grebeniuk
Ленту бесконечной памяти не приделать. Машина Тьюринга
концептуально мощнее любого компьютера, который может только
существовать.
R> Это еще почему? Я только знаю, что МТ мощнее любого компа,
R> эквивалентного МТ с конечной лентой. Hо ведь бывают еще
R> аналоговые компы, может, еще какие...
А они все эквивалентны в выразительной силе.
R> А я в это не верю. Как можно доказать эквивалентность
R> аналогового компа и МТ? Рассматривают матмодель. Только
R> модель почему-то всегда выбирают изначально такую, которая
R> уже содержит эквивалентность.

А вот доказали неэквивалентность квантовых контекстно-свободных грамматик и
дискретных контекстно-свободных грамматик. (g. про quantum languages
complexity)

Радостно?
Post by Serguey Zefirov
Или ты что-то другое имел в виду?
R> Я, когда написал о современных компах, имел в виду прежде
R> всего ГСЧ. Если мне докажут, что МТ+ГСЧ ~= МТ, буду
R> очень удивлен, но очень рад.

Ты бы расшифровал. А то мне непонятно.
Post by Serguey Zefirov
Post by Dmitry Grebeniuk
родится уважение к функциональным языкам, что уже само по себе
отлично :)
R> Спасибо, это я уже :-)
R> Уже успел ФЯ не только полюбить за красоту, но и невзлюбить
R> за то, что на практике ею ради эффективности приходится жертвовать,
R> как заглянешь куда-нибудь внутрь -- setq на setq сидит и progn'ом
R> погоняет. IO-монадами я, правда, так и не научился пользоваться.
Ага. ;)
Hачинай заново. ;)
R> Может, посоветуешь чего почитать именно про монады?
R> (Hе теорию категорий, а про практическое применение.)

Hу, у меня это произошло просто - я реализовал интерпретатор языка Joy и в
процессе все понял. ;)

Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
RockMover
2006-01-13 18:40:24 UTC
Permalink
Привет!

[...]
Post by Serguey Zefirov
А вот доказали неэквивалентность квантовых контекстно-свободных грамматик и
дискретных контекстно-свободных грамматик. (g. про quantum languages
complexity)
Что-то сходу не нагуглил.
Post by Serguey Zefirov
Радостно?
Еще нет, но выглядит многообещающе.
Post by Serguey Zefirov
Post by Serguey Zefirov
Или ты что-то другое имел в виду?
R> Я, когда написал о современных компах, имел в виду прежде
R> всего ГСЧ. Если мне докажут, что МТ+ГСЧ ~= МТ, буду
R> очень удивлен, но очень рад.
Ты бы расшифровал. А то мне непонятно.
Что непонятно, что машина Тьюринга слабее, чем она же,
дополненная генератором случайных чисел? Так я собственно
и надеялся, что мне тут ссылок накидают.

[...]
Post by Serguey Zefirov
Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
WBR, RockMover
I am The Master of Flame...
Serguey Zefirov
2006-01-13 19:33:18 UTC
Permalink
Post by Serguey Zefirov
А вот доказали неэквивалентность квантовых контекстно-свободных грамматик
и дискретных контекстно-свободных грамматик. (g. про quantum languages
complexity)
R> Что-то сходу не нагуглил.

Hабираешь в гугле и жмешь "Мне повезет."

Это самая первая ссылка.

Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
RockMover
2006-01-14 18:28:02 UTC
Permalink
Привет!
Post by Serguey Zefirov
Post by Serguey Zefirov
А вот доказали неэквивалентность квантовых контекстно-свободных грамматик
и дискретных контекстно-свободных грамматик. (g. про quantum languages
complexity)
R> Что-то сходу не нагуглил.
Hабираешь в гугле и жмешь "Мне повезет."
Уже нашел. Я сперва в кавычках набрал, а там не
"quantum languages complexity", а Complexity of Quantum Languages.
Post by Serguey Zefirov
Это самая первая ссылка.
Угу. Спасибо.
Post by Serguey Zefirov
Yours truly, Serguey Zefirov (thesz AT mail DOT ru)
WBR, RockMover
I am The Master of Flame...
RockMover
2006-01-13 18:40:23 UTC
Permalink
Привет!

[...]
Post by Serguey Zefirov
R> Может, посоветуешь чего почитать именно про монады?
R> (Hе теорию категорий, а про практическое применение.)
Думай о них как о методе организации кода, типа ООП или пакетов.
http://haskell.org/bookshelf/#monads
Морфизмы в каком-то смысле являются расширением (но не заменой)
монад. И, имхо, они гораздо проще для понимания.
http://haskell.org/arrows/
Морфизмы -- это arrows?
Post by Serguey Zefirov
http://haskell.org/arrows/biblio.html
John Hughes -- Generalising Monads to Arrows
Спасибо, пойду читать.


WBR, RockMover
I am The Master of Flame...
Ruvim Pinka
2006-01-18 07:56:12 UTC
Permalink
RockMover, wrote on 12.01.2006 19:12
Post by RockMover
Я, когда написал о современных компах, имел в виду прежде
всего ГСЧ. Если мне докажут, что МТ+ГСЧ ~= МТ, буду
очень удивлен, но очень рад.
Насчет "прикрутить" ГСЧ -- этот велосипед уже изобрели, до нас :)
-- вероятностная машина Тьюринга.

Также, и по "мощности" -- недетерминированная машина Тьюринга
(на основе которой определяется понятие NP-сложности).
С ней если что цифровое и сравнивается, так это, наверное, 'квантовый компьютер',
пока несуществующий.

Сылки: см. ru.wikipedia.org, и en.wikipeia.org "NP (complexity)"


--
Ruvim

RockMover
2006-01-11 16:12:31 UTC
Permalink
Привет!

[...]
Post by Alexander Zatvornitskiy
Вообщем, для начала можно таки познакомиться с машиной Тьюринга:) А
потом найти такого геймера:)
МТ чуть ли не в школе учат :-) Ну или на первом курсе. Аксиому выбора
тоже на первом курсе, но не везде :-)

[...]
WBR, RockMover
I am The Master of Flame...
Loading...