МБ
Полнота по Тьюрингу - это не бесконечность, а возможность реализовать любую вычислимую функцию. В реализацию вполне можно включать функуии: добавьте мне модуль памяти и взять значение по адресу http://x.y.z/любое-бла-бла-бла. Си Тьюринг-полный
Size: a a a
2020 January 27
AT
Полнота по Тьюрингу - это не бесконечность, а возможность реализовать любую вычислимую функцию. В реализацию вполне можно включать функуии: добавьте мне модуль памяти и взять значение по адресу http://x.y.z/любое-бла-бла-бла. Си Тьюринг-полный
Одна из "прелестей" (можно рассматривать её и как позитивную, и как отрицательную) машины Тьюринга - "любая вычислимая функция" включает в себя и машину Тьюринга тоже, так называемая "универсальная машина Тьюринга". Так что если вычислительная модель подразумевает наличие функции типа "дбавьте памяти", которую нельзя выразить с помощью той же самой вычислительной модели - то это слабоватая модель, и не ясно в каком смысле тогда на ней "можно реализовать любую вычислимую функцию".
МБ
Одна из "прелестей" (можно рассматривать её и как позитивную, и как отрицательную) машины Тьюринга - "любая вычислимая функция" включает в себя и машину Тьюринга тоже, так называемая "универсальная машина Тьюринга". Так что если вычислительная модель подразумевает наличие функции типа "дбавьте памяти", которую нельзя выразить с помощью той же самой вычислительной модели - то это слабоватая модель, и не ясно в каком смысле тогда на ней "можно реализовать любую вычислимую функцию".
Ну а в чём проблема? Это же конкретная машина с конкретной программой. Пишем на Си её реализацию, когда память на ленте кончается зажигаем лампочку: добавьте памяти. Насколько я понимаю, там важно не запустить эту реализацию, а предоставить её и доказать, что решение будет вычислять необходимую функцию, а не реально её вычислять.
МБ
Ну. Потому что, иначе, мы даже
+1 определить не сможем.А
Одна из "прелестей" (можно рассматривать её и как позитивную, и как отрицательную) машины Тьюринга - "любая вычислимая функция" включает в себя и машину Тьюринга тоже, так называемая "универсальная машина Тьюринга". Так что если вычислительная модель подразумевает наличие функции типа "дбавьте памяти", которую нельзя выразить с помощью той же самой вычислительной модели - то это слабоватая модель, и не ясно в каком смысле тогда на ней "можно реализовать любую вычислимую функцию".
Вообще на Си можно реализовать все те вычислимые функции, которые можно реализовать на железе (для которого есть компилятор Си). Этого достаточно для любого практического применения.
А
И я даже не знаю кого сильно волнует несоответсвие Си сферической машине Тьюринга в вакууме с бесконечной памятью.
AT
И я даже не знаю кого сильно волнует несоответсвие Си сферической машине Тьюринга в вакууме с бесконечной памятью.
Я тоже не знаю. Меня не волнует. Не понимаю, почему со мной пытаются спорить по этому поводу. 😂
K
Старая шутка про то, что C - это ассемблер для PDP-11, которая не шутка
TT
Тут есть, кто в LLVM IR разбирается
Есть статьи по типу «LLVM IR или как я написал свой компилятор»
Или «Моя жизнь после LLVM»?
Просто я даже в доках не могу понять пока, аккуратно всё, но всё друг на друге
Пытаюсь небольшой компилятор написать
Человекам нужно на следующей неделе показать/рассказать как пишутся компиляторы
А ля Калейдоскоп, только своё
Есть статьи по типу «LLVM IR или как я написал свой компилятор»
Или «Моя жизнь после LLVM»?
Просто я даже в доках не могу понять пока, аккуратно всё, но всё друг на друге
Пытаюсь небольшой компилятор написать
Человекам нужно на следующей неделе показать/рассказать как пишутся компиляторы
А ля Калейдоскоп, только своё
на github выложите, если не секрет?
RB
на github выложите, если не секрет?
когда оформлю, выложу))
МБ
Вопрос к коллективному разуму: не встречались ли какие-нибудь статьи о системе типов pony-lang? Там очень многообещающие утверждения о свойствах языка, а в пункте о системе типов ссылка на статью о сборщике мусора. У них там, конечно, какой-то codesign, но в самой статье о типах ничего внятного нет.
А⚙
Вопрос к коллективному разуму: не встречались ли какие-нибудь статьи о системе типов pony-lang? Там очень многообещающие утверждения о свойствах языка, а в пункте о системе типов ссылка на статью о сборщике мусора. У них там, конечно, какой-то codesign, но в самой статье о типах ничего внятного нет.
Там же в официальном FAQ есть ссылка на статью с доказательством корректности системы типов Pony
МБ
Там же в официальном FAQ есть ссылка на статью с доказательством корректности системы типов Pony
МБ
Она о сборке мусора.
МБ
Тоже интересная тема, конечно, но они там обещают очень много интересных статических гарантий. Это более заманчиво
МБ
AV
Вроде не все. Есть же тотальные языки: Idris, Sixten
Си, например, не Тьюринг полный ^_^
AV
Но причина почему это так на практике не важна