Чего не могут вычислительные машины: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 345:
# Равенство функций, вычисляемых двумя программами.
# Равенство нулю результата данной программы для определённых входных данных (наборе входных данных).
# Пустота (соответственно, и непустота) разрешимого множества,представленного программой, которая для каждого элемента может определить, принадлежит он этому множеству или нет.
# Определение количества шагов, которое сделает программа до завершения.
# Определение количества памяти, которое может понадобиться программе с динамическим выделением памяти.
# Определение, зависит или не зависит в программе значение одной переменной от значения другой.
# Определение, пройдёт ли когда-нибудь программа по данной ветви.
# Определение, являются ли два функциональных выражения частными случаями одного и того же.
# Существование положительных натуральных чисел <math>x_i</math>, таких что <math>P(x_1,\dots,x_n)=0,</math> где <math>P</math> — многочлен с целыми коэффициентами (наличия корня у диафантового уравнения).
# Существование решения произвольной системы уравнений в словах.
# Равенство либо неравенство (<math>\neq</math>, <math><</math>, <math>></math>) двух действительных чисел.
# Доказуемость логического утверждения с кванторами или же утверждения некоторой общепринятой формальной теории (арифметики, анализа и т. д.).
# Определение, переходит ли когда-нибудь данный двухголовочный автомат в состояние 0. (поскольку иначе можно было бы разрешить проблему остановки для машин Тьюринга).▼
▲# Определение, переходит ли когда-нибудь данный двухголовочный автомат в состояние 0. (поскольку иначе можно
==Практическая разрешимость==
| |||