Я читал, что изначально Черч предложил -calculus как часть своей статьи «Постулаты логики» (которая читается плотно). Но Клини доказал свою «систему» непоследовательной, после чего Черч извлек соответствующие вещи для своей работы по «эффективной вычислимости» и отказался от своей предыдущей...
Алгоритм быстрого умножения Карацубы был впервые опубликован в работах А. Карацубы и Ю. Офман (1962), "Умножение многозначных чисел на автоматических компьютерах", Труды Академии наук СССР 145: 293–294. Согласно Карацубе (1995, «Сложность вычислений», Институт математики им. В. А. Стеклова, 211:...
У меня есть два исторических вопроса: Кто первым описал недетерминированные вычисления? Я знаю, что Кук описал NP-полные проблемы, и что Эдмондс предложил, чтобы P-алгоритмы были "эффективными" или "хорошими" алгоритмами. Я искал эту статью в Википедии и пролистал «О вычислительной сложности...
Согласно (непроверенному) историческому описанию, Колмогоров считал, что каждый язык в имеет линейную сложность схем. (См. Предыдущий вопрос о гипотезе Колмогорова о том, что имеет цепи линейного размера .) Обратите внимание, что из этого следует, что .P P ≠ N PPP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq...
У меня совсем недавно была дискуссия о машинах Тьюринга, когда меня спросили: «Машина Тьюринга получена из автоматов или наоборот»? Конечно, я не знал ответа, но мне любопытно узнать. Машина Тьюринга - это немного более сложная версия автоматов Push-Down. Исходя из этого, я предполагаю, что машина...
Я учил нижних границ сегодня, и один из студентов спросил о причине названия C . Официальное объяснение состоит в том, что «А» означает «Чередование».AC0AC0AC^0A CAСAC Я смутно помню, как много лет назад мне сказали, что Ник Пиппенгер Стив Кук назвал честь Ника Пиппенджера (класс Ника), а позже Ник...
При попытке убедить экономистов в актуальности теории сложности в печати, есть ли стандартная ссылка для цитирования? Я знаком с постом в блоге Ноама Нисана , опросом Тима Раугардена и 11-й статьей эссе Скотта Ааронсона . Эти посты доступны для компьютерных ученых, но не используют язык экономистов...
Существуют ли интересные примеры алгоритмов, которые были опубликованы с проверенными границами, и где позже были опубликованы строго лучшие оценки? Не лучшие алгоритмы с лучшими оценками - очевидно, что это случилось! Но лучший анализ ведет к лучшей оценке существующего алгоритма Я думал, что...
Я интересуюсь ранней историей опубликованных результатов о пространственно-временных компромиссах общего назначения. В частности, я хочу знать, кто первым описал следующий тип алгоритма для вычисления вычисления, имеющего произвольный граф потока данных с степенью O (1), используя пространство,...
Кто представил идею рекурсии ? Может кто-нибудь объяснить, откуда он взялся и как он повлиял на
Робин Милнер определил биграфы как тип графической структуры с графоподобной структурой, где узлы могут быть вложенными. Они обобщают исчисления процессов, такие как CCS и калькуляция, но Мильнер, похоже, намеревался использовать их гораздо более широко: в записках семинара незадолго до его смерти...
Обучая, как реализовывать автоматы с использованием синхронных логических схем, я заметил интересное совпадение: как в теоретическом мире CS, так и в мире электротехники «состояние» обычно обозначается как (и пространство состояний Q ). Сначала я спросил об EE.sx , но затем, немного исследуя эту...
Чтобы отпраздновать 100-летие Алана Тьюринга, я хочу посмотреть документальный фильм о его жизни. Однако есть несколько документальных фильмов на выбор. Какой документальный фильм об Алане Тьюринге ваш любимый? Пожалуйста, включите только один документальный фильм за...
Я хотел бы знать об истории этих двух терминов: « эффективный », « выполнимый ». Кто использовал их в отношении вычислений / алгоритмов в первый раз? (в современном понимании этих терминов, т.е. 20-го века). Как они стали мейнстримом? Как эти два термина начали использоваться как синонимы? Я знаю,...
Я ищу: Майкл О. Рабин, «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств», Еврейский университет, Иерусалим, 1960 Резюме: «Мы пытаемся измерить объем работы, свойственный задаче вычисления заданной вычислимой (рекурсивной) функции. Представлено и изучено понятие...
Языки Dyck определяются следующей грамматикой S → S SDyck(k)Dyck(k)\mathsf{Dyck}(k) над множеством символов { ( 1 , … , ( k , ) 1 , … , ) k } . Интуитивно понятно, что языки Dyck - это языки сбалансированных скобок k различного типа. Например, (S→SS|(1S)1|…|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S \rightarrow...
Я пытался обернуть голову вокруг того, что, почему и как вычислить, но я не могу понять, «почему это работает»?λλ\lambda «Интуитивно» я получаю модель вычислимости машин Тьюринга (ТМ). Но эта абстракция просто оставляет меня в замешательстве.λλ\lambda Давайте предположим, что ТМ не существуют -...
Все известные мне компьютерные музеи и экспонаты, кажется, охватывают только историю вычислительной техники, но не затрагивают темы компьютерных наук. Вы участвуете в создании нового Музея вычислительной техники, созданного для обучения, развлечения и привлечения широкой публики к широкому кругу...
Хорошо известно, что аналитическая машина Чарльза Бэббиджа имела архитектуру, сильно напоминающую современную архитектуру фон Неймана. Также примечательно, что таблицы для представления программы для аналитической машины Бэббиджа ( http://www.fourmilab.ch/babbage/figures/menat3.png ) и работы фон...
(Извинения, если это неуместно или слишком широко. Я открыт для предложений о том, как это переформулировать.) Я заинтересован в отслеживании "древней" истории алгоритмов максимального потока и алгоритмов дискретной оптимизации в целом. Форд-Фулкерсон мой соломенный стартовый пункт. Каковы были...