Описание тега computability
2
ответа
Тьюринг-полнота модифицированной версии Brainfuck
Является ли Brainfuck Turing-завершенным, если ячейки являются битами, а операции + и - просто слегка меняются? Есть ли простое доказательство того, что языки, подобные Brainfuck, полны по Тьюрингу независимо от размера ячейки, или мне нужно подумат…
22 дек '12 в 23:19
1
ответ
Включает ли полнота по Тьюрингу способность ничего не делать
Необходимо ли, чтобы языки могли представлять "ничего не делать", чтобы считаться завершенным по Тьюрингу? Если ответ "нет", то существует мыслимая программа, которая не может быть представлена / выполнена на компьютере, завершенном по Тьюрингу, н…
21 фев '18 в 20:00
1
ответ
Способы измерения сложности битовой последовательности
Я ищу простой способ оценить сложность последовательности битов фиксированного размера (возможно, максимальная длина 10). Например, я думаю, что 0000000 и 111111 совсем не сложны, но 101010 и 101101 находятся в другом месте спектра. Я знаю, что слож…
19 июн '15 в 20:27
1
ответ
Эмуляция числовых операций в программном обеспечении
Числовые операции, которые мы выполняем в наших программах, ограничены количеством байтов, которые язык определяет для данного типа данных (или, возможно, поддерживает аппаратное обеспечение). Скажем, я могу использовать целочисленные значения для р…
29 окт '10 в 19:48
1
ответ
Расширенная реализация алгоритма GCD Лемера
Делая мою собственную реализацию BigInteger, я застрял с расширенным алгоритмом GCD, который является фундаментальным для нахождения модульного мультипликативного обратного. Поскольку хорошо известный евклидов подход подходит слишком медленно, а гиб…
07 июн '13 в 17:21
9
ответов
Разве решение проблемы остановки легче, чем думают люди?
Хотя общий случай неразрешим, многие люди все еще решают проблемы, которые достаточно хорошо подходят для повседневного использования. В докторской диссертации Коэна о компьютерных вирусах он показал, что сканирование на вирусы эквивалентно проблеме…
02 сен '08 в 21:25
2
ответа
Может ли функция разбора rebol быть в состоянии создать правила для полного разбора css2 / css3?
Есть ли ограничения для ребол функции питания? Будет ли он способен анализировать всю спецификацию css2 / css 3 или он столкнется с теоретической невозможностью сформировать некоторые правила? Обновление после ответа HostileFork: я имею в виду в рег…
14 авг '10 в 19:42
0
ответов
Показывает ли мое решение, что язык не вычислим, если применить теорему Райса?
Если p машина Тьюринга, то L(p) = {x | р (х) = да}. Let A = {p | p is a Turing machine and L(p) is a finite set}. Является ли вычислимым? Обосновать ответ. Поэтому я пытаюсь выяснить, как решить этот вопрос, и вот ответ, который я придумал: (i) Итак…
13 ноя '18 в 23:15
1
ответ
Разрешимость и рекурсивная перечислимость
Скажем, существуют машины Тьюринга M1, M2, M3, которые они распознают как L (M1), L (M2) и L (M3) соответственно. Следующий язык L = {(M1, M2, M3): L(M1), L(M2) и L (M3) не равны} Является ли язык разрешимым? Рекурсивно перечислимый? Или нет?
10 мар '12 в 05:37
4
ответа
Сложное поведение, генерируемое простым вычислением
Стивен Вольфрам дал увлекательную беседу на TED о своей работе с Mathematica и Wolfram Alpha. Среди прочего он указал, как очень простые вычисления могут привести к чрезвычайно сложному поведению. (Он продолжает обсуждать свои амбиции по вычислению …
04 май '10 в 07:53
0
ответов
Решив, жилье?
Рассмотрим базовую систему простых типов, обычно известную как TAλ. Это можно доказать (как следствие так называемого свойства сокращения объекта и того факта, что любой типизированный член сильно β-нормализует) If τ has an inhabitant, then it has o…
21 авг '13 в 19:53
4
ответа
Понимание Σ* и Σ в формальных языках
Если у меня есть Σ={a} какие слова делают Σ* имеет? Σ*= {a,aa,aaa,aaaa.....}? Спасибо
27 июл '12 в 15:09
1
ответ
Может ли машина Тьюринга решить, завершена ли формальная модель вычислений?
То есть может ли машина Тьюринга взять формальную систему S в качестве входных данных и решить, является ли S полной по Тьюрингу? Я думаю, что это неразрешимая проблема, я прав? Если это неразрешимо, почему мы (как люди) можем решить полноту Тьюринг…
19 апр '13 в 17:41
1
ответ
Вычислимость задачи теории вероятностей
Это проблема, которую я решил для курса, и мне было интересно, если мое решение является правильным. Я бы не стал публиковать проблемы чистой математики, кроме того, что я считаю, что это неисчислимо, и, следовательно, проблема информатики. Тебе дал…
27 дек '10 в 19:14
10
ответов
Что такое машина Тьюринга?
Что такое машина Тьюринга и почему люди продолжают упоминать ее? Мой IBM PC - это все, что мне нужно для вычислений! Почему кто-то заботится об этих машинах?
25 окт '08 в 06:25
1
ответ
Сводимость этм неразрешима
Я хочу спросить о сокращении. В доказательстве того, что Etm неразрешима в определении M1, 1. если x!= W, отклонить 2.Если x==w,запустите M на входе w и примите M, если Во многих доказательствах, которые я встречаю, я вижу эту жирную линию, но я не …
04 июл '17 в 10:28
1
ответ
Снижение от банкомата до банкомата
Есть ли сокращение от банкомата до банкомата? Я слишком много думал об этом и не смог найти ответ. Я знаю, что сокращение от ATM-дополнения до ATM невозможно, потому что если бы оно было, банкомат не был бы в RE. Но как я могу доказать / сделать нао…
26 янв '16 в 19:52
4
ответа
Является ли класс функций поли-времени рекурсивно перечислимым?
Если я определяю функции Poly-time, то функции, которые вычисляются машиной Тьюринга за максимальное полиномиальное (n) время, n - это размер входных данных. Является ли класс этих функций рекурсивно перечислимым?
16 фев '11 в 15:29
1
ответ
Докажите, что конкретный язык не является полуразрешимым
Я должен доказать, что язык L = {: |L(M)| <= 2016} НЕ является полуразрешимым. Теперь я подумал сделать это так: Возьмем случайный алфавит E. Теперь в E. есть бесконечное количество слов. Мы можем только заключить, что | L (M) | <= 2016, передавая к…
28 май '17 в 14:01
1
ответ
Может ли программа решить, останавливается ли произвольная программа для некоторого ввода?
Существует ли программа (may-halt? P), которая может определить, существует ли вход, чтобы (p input) останавливался? Я попробовал простую диагонализацию, но она только говорит мне, что (may-halt? Diag-may-halt) должно быть правдой. Это не помогает д…
28 июл '15 в 18:24