LINUX.ORG.RU

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


0

0

Несколько раз в топиках встречался сабж применительно к языку программирования. AFAIK, полнота какой-либо формальной логики - означает, что есть набор аксиом+правил вывода, а все остальное может быть выведено из этих аксиом посредством механизма вывода. Например, исчисление высказываний полно. Что означает полнота ЯП?


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

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

Язык программирования называется 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...

ringill ()

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

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

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

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

ukez ()
Ответ на: Re: Тьюринг-полнота от ukez

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

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

vsl ()
Ответ на: Re: Тьюринг-полнота от ukez

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

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

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

Motl ()
Ответ на: Re: Тьюринг-полнота от ukez

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

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

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

dilmah ★★★★★ ()
Ответ на: Re: Тьюринг-полнота от dilmah

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

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

vsl ()
Ответ на: Re: Тьюринг-полнота от stalkerg

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

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

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

dilmah ★★★★★ ()
Ответ на: Re: Тьюринг-полнота от aa5779

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

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

vsl ()
Ответ на: Re: Тьюринг-полнота от vsl

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

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

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

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

lb ()
Ответ на: Re: Тьюринг-полнота от lb

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

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

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

vsl ()
Ответ на: Re: Тьюринг-полнота от vsl

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

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

lb ()
Ответ на: Re: Тьюринг-полнота от lb

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

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

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

int19h ★★★★ ()
Ответ на: Re: Тьюринг-полнота от vsl

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

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

lb ()
Ответ на: Re: Тьюринг-полнота от lb

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

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

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

int19h ★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.