Тьюринг-полнота

Примерно так:

Язык программирования называется Turing-complete тогда, когда он по вычислительным возможностям эквивалентен машине Тьюринга. То есть для любой программы, записанной на ленте этой машины, можно написать программу на данном языке, которая при тех же входных данных будет давать тот же результат.

Машина Тьюринга теоретически может всё, что могут современные компьютеры, и даже больше (т.к. лента у неё бесконечная). Есть т.н. тезис Чёрча (Church), утверждающий, что машина Тьюринга может вычислить всё, для чего человек может определить формальную процедуру вычисления).

Большинство используемых в программировании языков (процедурные, функциональные, объектно-ориентированные) полны по Тьюрингу. Примеры не Turing-complete языков -- язык конечных автоматов, язык стековых автоматов (автоматов с магазинной памятью).

http://en.wikipedia.org/wiki/Turing_machine

http://en.wikipedia.org/wiki/Church-Turing_thesis

http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8...

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D0%B5%D1%8...

Мое предположение (я в этих делах полный тьюринг, но думаю моя мысль логична):

Тьюринг-полнота означает что на данном языке можно решить любую в принципе вычислимую задачу.

Также предположу что у большинства попсовых языков ( Це, Паскаль )проблемма с средствами метапрограммирования и потому они Тьюринг-неполные. На них низя написать программу, которая сама пишет другую программу и выполняет ее (путано изложил, но суть я думаю уловима)

Ты на Цэ, на Васике, на ПостСкрипте, на XSLT, на bash-е и даже на command.com-е можешь написать симулятор машины Тьюринга - следовательно, они - Тьюринг-полные.

ну ваще да. видимо я не прав.

>Также предположу что у большинства попсовых языков ( Це, >Паскаль )проблемма с средствами метапрограммирования и потому они >Тьюринг-неполные. На них низя написать программу, которая сама пишет >другую программу и выполняет ее (путано изложил, но суть я думаю >уловима)

Очень расплывчато и малоубедительно.

> Также предположу что у большинства попсовых языков ( Це, Паскаль )проблемма с средствами метапрограммирования и потому они Тьюринг-неполные.

доля истины в этом есть -- в том что препроцессор Си Тьюринг-неполный.

Однако, Тьюринг-полнота сама по себе не достаточна. Темплейты C++ - Тьюринг-полный язык, но это вовсе не значит, что на них можно сделать всё, что можно сделать на C++.

Как видемо я такой эмулятор инаписал. Делать было нечего....

> Как видемо я такой эмулятор инаписал. Делать было нечего....

в смысле?? ты ж его на Си писал а не на препроцессоре..

Каким это боком templateы --- это Тьюринг-полный язык???

Таким, что на них симулятор МТ или лямбды написать можно.

P.S. вот красивое доказательство:

http://homepage.mac.com/sigfpe/Computing/sk.html

> Темплейты C++ - Тьюринг-полный язык

с чего бы набор умных макросов для языка стал языком ?

Мда, действительно, мог бы и сам сообразить :)

Вот именно с Тьюринг-полноты и стал.

Язык макр может и вовсе совпадать с host-языком - как в Лиспе, или в Jatha.

> http://homepage.mac.com/sigfpe/Computing/sk.html

Действительнно красиво. Только темплейты там не язык, а лишь одна из конструкций языка.

PS. синтаксических конструкций языка для циклов много. но не это не значит, что если чего-то можно красичо сделать через while, то while это язык.

А наследование это теперь часть Темплейтов ?

Нет, там язык - это как раз шаблоны, остальное - обвязка.

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

Ты это к чему?

к тому что _тот_же_ код можно получить без темлейтов. ручками. а вот без конструкции наследования код уже будет другим.

> с чего бы набор умных макросов для языка стал языком ?

Советую поковыряться в архивах форума, и найти написанную (мной ;) Game
of Life целиком на плюсовых темплейтах.

Незачот. Приходите на пересдачу.

не _на_ темплейтах, а с их использованием. _на_ темплейтах написать ничего нельзя.

Ты очень, очень глупый человек. Тебе не стыдно?

для меня просто счаятье, когда у "поселковых гуру" кончаются заученные , но не понятые аргументы и остаются только дешевые понты.

> к тому что _тот_же_ код можно получить без темлейтов. ручками. а вот
> без конструкции наследования код уже будет другим.

О да, конструкция наследования - это просто-таки необходимейший
механизм в вычислительных задачах...