Машина тьюринга

У нашего клоуна есть тред и про то, что формальные теории - говно, потому что, видите ли, «гедель доказал, что ничего невозможно доказать» (отрицательный iq источника сохранен).

устами младенца (:

Если серьёзно, то сама по себе мысль правильная. Я надеюсь, что ТСу меньше 20и лет от роду. Тогда он сможет придумать и ещё что-то ценное, а не только это.

Формальные теории в некотором смысле действительно «говно». Это правда. Есть правда две проблемы:

1. хоть они и «говно», но годны и полезны для практики

2. других теорий у нас нет и быть не может. Ну что бы с п1.

Я вижу вонючее быдло твою ущербность насквозь. Поэтому ты так боишся подрыва основ. Мне срать на твои баны и архивы, неполноценная мразь, это только такое ничтожество как ты может беспокоить. Беги обратно к мамочке под юбку.

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

зачем ты на ЭТО отвечаешь? Ведь одним своим ответом ты соглашаешься с там, что твой интеллектуальный потенциал равен потенциалу собеседника. Но т.к. ты оцениваешь его потенциал ничтожным, то следовательно...

Что будет, если отнять больше яблок чем у меня есть

будешь должен. Очевидно жеж!

Я почитал в свое время про натуральные числа и действительные числа. Толком ни хрена не понял идею.

на самом деле, можно и на яблоках продемонстрировать комплексные величины. Ты просто их действительно не понимаешь. Просто тупо вызубрил...

Но слишком сложны для формализации.

ну придумай лучше. С удовольствием ознакомлюсь, ибо мне сабж тоже не нравится.

МТ удобно программируется, и достаточно проста для формализма. Что тебе ещё надо?

Моя основная претензия в том, что МТ пытается нам навязать мысль о том, что память является необходимым компонентом вычислений. Это введение взаблуждение, мягко говоря. Память является удобной фичей, но не является необходимостью. Концепция «эффективной вычислимости» учит нас тому, что мы в формализации должны отделять удобное от необходимого. Поэтому, я считаю, что в качестве формальной системы МТ не годится.

Имхо bf-машина будет сложнее какого-нибудь 8080.

а ты не имхуй, а погугли. Они уже есть, из говна, палок, и светодиодов АЛ307.

В ассемблерах нет понятия парной скобочки.

call/ret для x86

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

И-НЕ или ИЛИ-НЕ могут являться базисом. Т.е. если у тебя есть возможность построить И-НЕ, то соединив их в нужном порядке можно получить И, НЕ, ИЛИ и всё остальное. Одним И не обойдёшься.

Читай: «функция следущего шага вычислений». Такая же функция, как та, что в лямбда-исчислении задаёт бета-редукцию. Именно в этом пошаговости и лежит вся соль вычислений.

Одним И не обойдёшься.

Я сказал И и НЕ

Моя основная претензия в том, что МТ пытается нам навязать мысль о том, что память является необходимым компонентом вычислений.

А, ну то есть «текущее состояние ленты» в машине Тьюринга неприемлемо, а «текущий терм» в лямбда-исчислении — это ок?

Во многих физических способах реализации логики элемент И элементарным не является. Например в майнкрафте элементарны НЕ и ИЛИ, а наиболее просто реализуется элемент И-НЕ.

Мне кажется, принципиальная разница тут в том, что МТ явно указывает шаг - записал - нашел - прочитал. В LC шаг редукции подразумевает отношение эквивалентности. Там нет явной необходимости работы с памятью (лентой). МТ нам навязывает мысль, что память - необходимый компонент вычислений. Причем реализация скрыта. Я уже писал об этом здесь

Текущий терм не принято понимать в смысле шага во времени и состояния. Иначе Y-комбинатор - это подлог. Нет там текущего состояния.

Во многих физических способах реализации логики элемент И элементарным не является.

Это не важно. Важно то, является ли он таковым концептуально.

а наиболее просто реализуется элемент

В электронике и электротехние проще всего реализуется элемент и, поскольку это 1 транзистор.

Мне кажется, принципиальная разница тут в том, что МТ явно указывает шаг - записал - нашел - прочитал.В LC шаг редукции подразумевает отношение эквивалентности.

Машина Тьюринга: было одно состояние (всей системы), по правилам перешли в другой состояние.

Лямбда-исчисление: был один терм, по правилам редуцировали в нём что-то и получили другой терм.

Лично я не вижу разницы и какой-то необратимости этих преобразований.

Причем реализация скрыта.

Напомни, где там хранятся термы лямбда-исчисления?

Не распарсил.

К тому же эта модель с памятью очень хреново ложится, к примеру на CPS, поскольку не позволяет непосредственно передать другому вычислителю результат вычислений, минуя сохранение промежуточного состояния.

концептуально

Человекам он может быть и концептуальнее. А так и И, и И-НЕ — просто определённые таблицы истинности. И если в качестве базиса можно взять одну таблицу вместо двух, почему бы так не сделать?

Начиная с этого сообщения и далее обсуждалось. Не буду повторяться. Пробежитесь глазами постов 5-6.

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

Об этом ваще-то в любом техническом ВУЗе рассказывают.

Суть в том, что с чего ты решил, что «элементарна» именно операция «И»? Из-за русского языка только? Ну дык в русском языке полно нелогичностей, например элементарна «корова». Хотя её реально можно разделить на «корова без вымени» и «вымя». Ну и что? Ну нет в русском слова для «корова без вымени», что делать? Для операции «И-НЕ» тоже нет слова.

Однако, если ты возьмёшь почти любую функцию(кроме вырожденных и тривиальных), ты увидишь, что их можно разделить на И-НЕ, но никак нельзя на И или ИЛИ. Т.о. функции И и ИЛИ нельзя признать «элементарными», как и «корову».

Даже саму функцию И-НЕ нельзя выразить никакой комбинацией И и/или ИЛИ.

Просто ШТРИХ ШЕФФЕРА это не так коротко, как И-НЕ.

Напомни, где там хранятся термы лямбда-исчисления?

Да мы не должны об этом думать в этих категориях. Нужно думать об этом как будто сразу происходит подстановка. Например, (/x.x)(/x.x) - это уже /x.x. имена - не важны, промежуточных состояний нет. Важны сами «метаморфозы». Другой уровень абстракции. Ну я так понимаю, а там - хз.

Даже саму функцию И-НЕ нельзя выразить никакой комбинацией И и/или ИЛИ.

Как это нельзя? Во первых, мы не о функциях, а об элементах. А элемент И-НЕ, - это комбинация И и НЕ. Не надо все усложнять.

Я сказал И и НЕ

дык две функции по твоему «элементарны», а вот одна — уже почему-то нет?

с чего ты решил, что «элементарна» именно операция «И»

Тупо потому, что у тебя есть элемент цепи И, потом ты добавляешь в него НЕ, и получаешь И-НЕ. Как одна горошина более элементарна, чем 2.

Что ты можешь сделать, если у тебя есть только И? Каждая из них элементарна. Их комбинации порождают все остальное.

В электронике и электротехние проще всего реализуется элемент и, поскольку это 1 транзистор.

facepalm.

Один транзистор — это элемент НЕ. Если на вход подаёшь высокий потенциал, транзистор открывается, и на выходе низкий.

Вот используя диоды, или соединяя вместе транзисторы, ты получаешь И-НЕ или ИЛИ-НЕ.

http://sub.allaboutcircuits.com/images/04125.png

Элемент И состоит из элементов И-НЕ и НЕ.

А элемент И-НЕ, - это комбинация И и НЕ. Не надо все усложнять.

покажи мне в схемотехнике элемент «И» или «ИЛИ» с транзистором. У меня что-то не получается такой соорудить. Из двух диодов получается сделать ИЛИ, проблема в том, что всё равно нужны усилители между этими элементами. А усилители — таки НЕ.

Это все ботаническая чушь. Я не об этом. Транзистор способен принять на базу и эмиттер 2 сигнала. Если оба сигнала(и тот и этот) присутствуют он откроется, и пойдет выход на коллектор. Это концептуально = элемент И. Любое реле промежутка также является И. В качестве НЕ пойдет любой разрыв цепи.

когда транзистор откроется как раз будет на выходе 0 а не 1.

http://sub.allaboutcircuits.com/images/04125.png

угу. И->НЕ->НЕ.

Я что-то не понял, о чём там речь и как это мешает пошаговости. Есть терм g. Есть терм Y, который λx.(λy.x(yy))(λy.x(yy)). Редуцируем Y g. Получаем (λy.g(yy))(λy.g(yy)). Редуцируем ещё разок: g((λy.g(yy))(λy.g(yy))). И вот тут анон спотыкается, потому что типа "((λy.g(yy))(λy.g(yy))) — это не же тот (λy.g(yy))(λy.g(yy)), который получен одной редукцией назад, а если тот, то мы завязаем в бесконечном цикле, потому что редуцировав его, получаем gg(λy.g(yy))(λy.g(yy))". Но ведь редуцировать дальше можно аппликацию g к (Y g). И тогда g решит, продолжать рекурсию или нет.

А что не так, если отбросить ботаническое задротство?

Транзистор способен принять на базу и эмиттер 2 сигнала. Если оба сигнала(и тот и этот) присутствуют он откроется, и пойдет выход на коллектор. Это концептуально = элемент И.

не. Транзистор откроется, и на выходе будет 0. При этом на базе должен быть 1, а на эмиттере 0.

0 0 1
0 1 1
1 0 0
1 1 1

Любое реле промежутка также является И. В качестве НЕ пойдет любой разрыв цепи.

facepalm ещё раз...

Что ты можешь сделать, если у тебя есть только И?

Имея только И, можно выразить n-арную логическую операцию И. Всё.

А имея только И-НЕ, можно выразить любую логическую операцию любой арности.

Не понял, почему там будет 0, если на коллекторе будет сигнал присутствовать.

Так я и говорю, что И и НЕ, их комбинации, позволят выразить все что угодно.

Да ты просто не можешь отличить чистую логику от задротской реализации. Просто подумай над этим еще раз, не спеши с ответом.

Еще раз: любой элемент который принимает на вход 2 сигнала и выдает (или не выдает) на выход третий, уже, по факту, КОНЦЕПТУАЛЬНО, является элементом И.

А что не так, если отбросить ботаническое задротство?

концептуально, используя И и ИЛИ ты никогда не получишь из нуля единицу, и наоборот. Т.е. ни тот, ни другой на роль «элементарных» не тянут.

Из элементов И и ИЛИ можно строить только другие элементы И и/или ИЛИ. Даже XOR и то не получается.

Так я и говорю, что И и НЕ, их комбинации, позволят выразить все что угодно.

так тебе и говорят, что резать И-НЕ на части не нужно.

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

Еще раз: любой элемент который принимает на вход 2 сигнала и выдает (или не выдает) на выход третий, уже, по факту, КОНЦЕПТУАЛЬНО, является элементом И.

facepalm... И да, мне тоже отсыпь этой концептуальной из Чуи.

концептуально, используя И и ИЛИ ты никогда не получишь из нуля единицу, и наоборот. Т.е. ни тот, ни другой на роль «элементарных» не тянут.

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

Хорошо, дай мне четкое внятное и простое определение И. С точки зрения того, что он делает, а не конкретную реализацию.

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

И, конечно, это делается МАГИЕЙ, а не подключением элемента НЕ, который принципиально отличается от И и ИЛИ.