На двух логических элементах И и НЕ или ИЛИ и НЕ можно построить тьюринг-полную логику, что и делается в матрицах КМОП 2И-НЕ. Уж тем более тьюринг полна логика первого порядка.
@je Внезапно, цикл (алгоритм) можно реализовать только схемой, в которой есть циклы из элементов. Схема без циклов представляет собой конечный набор формул логики нулевого порядка и берёт конечное число входов и однозначно преобразует их в конечный набор выходов. И это никак не является тьюринг-полным (контрпример: функция, берущая n и возвращающая n едениц и 1 ноль в конце). Если навернуть сверху цикл, который сохраняет вход и кормит его выходу, то получится самый обычный конечный автомат, который уже может реализовать любую вычислимую функцию.
@anonymous Слышь, ебанашка, 2И-НЕ является тьюринг-полным. SKI-базис комбинаторов тоже тьюринг-полный. Чо ты пропиздел я тебя не понял, на 2И-НЕ можно сделать RS-триггер и хранить состояния. Мудачье бля.
@je В триггере как раз таки есть цикл. Да, 2И-НЕ без ограничений на циклы является. На самом деле я, когда читал ОП-пост, перепутал логику первого и нулевого порядка. Логика нулевого порядка не является Тьюринг-полной, логика первого хрен его знает, нужно как-то хитро сопоставить программу логической формуле, а может и не хитро, но я тупой и мне лень. "Уж тем более" из /TOF тут совсем не очевидно.
@je Без циклов в схеме можно вычислить только ограниченное число вычислимых функций, так что вроде бы всё-таки нет.
@je Внезапно, цикл (алгоритм) можно реализовать только схемой, в которой есть циклы из элементов. Схема без циклов представляет собой конечный набор формул логики нулевого порядка и берёт конечное число входов и однозначно преобразует их в конечный набор выходов. И это никак не является тьюринг-полным (контрпример: функция, берущая n и возвращающая n едениц и 1 ноль в конце). Если навернуть сверху цикл, который сохраняет вход и кормит его выходу, то получится самый обычный конечный автомат, который уже может реализовать любую вычислимую функцию.
С первым порядком хрен знает, что там.
@je В триггере как раз таки есть цикл. Да, 2И-НЕ без ограничений на циклы является.
На самом деле я, когда читал ОП-пост, перепутал логику первого и нулевого порядка. Логика нулевого порядка не является Тьюринг-полной, логика первого хрен его знает, нужно как-то хитро сопоставить программу логической формуле, а может и не хитро, но я тупой и мне лень. "Уж тем более" из /TOF тут совсем не очевидно.
http://arxiv.org/abs/1405.1715