16-й: Все сообщения за 16 Ноября 2021 года

16-й>> Вроде ж не "можно написать", а что где-то там, в бесконечном множестве бинарного кода произвольной длины, существует эта самая программа. Что, как мне кажется, не одно и то же.
Zenitchik> Нет. Именно, что можно реализовать любой алгоритм. Полнота по Тьюрингу.

Ну, то я криво выразился. Понятно, что если такая последовательность кода в принципе существует, то можно ее реализовать. Опять же в принципе. Но в практическом смысле это мало что дает.
Вообще, некое недоумение от машины Тьюринга у меня осталось еще со студенческих времен. Тем более, что нам ее давали без объяснения, на кой она понадобилась самому Тьюрингу. А он, как я позже узнал, хотел "переформулировать" теорему Геделя. Т.е. решал чисто математическую задачу, имеющую к программированию (в курсе которого она появилась у нас) весьма странное отношение.
Что характерно, я потом спрашивал разных коллег-программеров, что они думают про машину Тьюринга - все как один отвечали в духе "непонятно на кой черт она вообще нужна".

Zenitchik> ...состоящей только из элементов ИЛИ-НЕ. Там ничего сложного, громоздко только.

Ну, так это ж вроде очевидно, или я чего-то не понял в посыле? Еще ж с младых ногтей доказывается, что через и-не / или-не можно построить все прочие "элементарные" булевы функции, а из тех уже все прочее.

•  12
•  инфо
•  инструменты
• Ответить на сообщение