Машина тьюринга

мне кажется, тут где-то зарыта истина

Главное знать общий принцип, а детали могут быть реализованы 100500-ми способами. Разбираться в каждом смысла нет, главное знать принцип, тогда можно разобраться с тем, что перед тобой предстло.

Ни машина Тьюринга, ни машина Поста не предназначены для того, чтобы на них буквально решали какие-то практические задачи, это чисто теоретические абстракции. Выдыхай

В том то и дело, что понимания «общего принципа» они не дают.

Так я как раз о теории и говорю.

У тебя поломалось абстрактное мышление.
Ты из тех людей, которые от изменения интерфейса выпадают в осадок и зовут папу.
Мы не будем тебе ничего объяснять, так как это бесполезно — ты либо неимоверно туп, либо тролль.

Тренируй скил логического мышления:

1-ый раз читаешь статью, формулируешь для себя общие цели и задачи о которых в статье идёт речь. Отмечаешь места, которые остались не совсем ясными.

2-ой раз читаешь с целью разобраться в тёмных пятнах, используя другие источники.

Тогда зачем тебе знать детали их реализации? Они никак не реализованы, это модели.

Обозначеный в последнем предложении вопрос, меня ещё с темы про программирование без процессора волнует. Не могу понять, что есть на самом деле.

Однако замечу, что все вышесказанное относиться как раз к тебе. Ты ненамеренно сейчас, произвел свое собственное метаописание, причем тему не понял, что тоже намекает.
No comments

Ну, они вообще-то реализованы, кроме «бесконечной ленты», но сути это не меняет, паровозы и пароходы тоже реализованы.

Ну, они вообще-то реализованы, кроме «бесконечной ленты»

Это называется «не реализованы». Но даже если бы где-то и существовала идеальная машина Тьюринга, что бы это изменило в теоретических выкладках?

Ты про сложность?
Ну даже не знаю.
Определение не обязано быть простым. Невозможно ведь сложную вещь описать просто:)

Да ничего бы не изменило. Я считаю претензии этих машин на формализацию вычислений необоснованными. С таким же успехом на это мог бы претендовать какой-нибудь бейсик. В них изнчально присутствует некоторый «интерфейс», а этого быть не должно, на мой взгляд.

Сделай машину проще. А физическую реализуемость тебе никто и не обещал, где ты возьмешь бесконечную ленту для машины Тьюринга?

Ок. Тогда есть 4 непротиворечивых друг другу варианта:
1) Ты неимоверно туп
2) Я неимоверно туп
3) Ты тролль
4) Я тролль

Комплектуй ноборчик:)

Физическая реализуемость не требуется. Об этом вообще разговора нет.

Определение не обязано быть простым

Обязано. Иначе мы вместо доказательства получаем очередное бездоказательное определение. Можешь считать, например, что теорема о равенстве треугольников легким движением руки превращается в аксиому о рвенстве треугольников.

В том то и дело, что понимания «общего принципа» они не дают.

есть общий принцип вычислителя. Есть память, и есть исполнитель. Все.

Обязано.

Не-а. Определение должно охватывать общие черты целого класа определяемых хреней. За счёт абстрагирования от некоторых подробностей мы получаем общее определение, которое ПРОЩЕ, чем точное определение каждой хрени в отдельности.
Но простым определение быть не обязано.
ПРОЩЕ чем СЛОЖНОЕ не значит ПРОСТО. Уловил мысль?
А ТСу не нравится именно абсолютная сложность абстрактной системы.

Ну хорошо, тогда получается, что вычислитель тут нам дан «свыше», а формализован процесс взаимоедйствия вычислителя с памятью. Но интересна то как раз формализация вычислителя. А эта хрень и так любой домохозяйке понятна. Где профит тогда?

Уловил мысль?

Уловил и не спорю. Но в данном случае формализована работа вычислителя с данными. А это не интересно.

С таким же успехом на это мог бы претендовать какой-нибудь бейсик

Мог бы. Разве кто-то утверждает обратное?

как происходит переход между ячейками ленты. Как головка идентифицирует символ метки. Как она может быть одновременно и средством записи и ср-вом чтения

Геометрия в школе тебя не смущала? Точки, линии, острые углы?

Ну и что. Что нам машина тьюринга говорит об этом?

Ну хорошо, тогда получается, что вычислитель тут нам дан «свыше», а

почему же свыше? Тьюрингом же дан.

формализован процесс взаимоедйствия вычислителя с памятью. Но интересна то как раз формализация вычислителя.

вот это и есть формализация. Если не нравится - формализуй по другому.

Это как точка в геометрии или идеальный газ в физике — в реальном мире их не существует, но объекты в определённых рамках могут быть ими описаны.

Ну, они вообще-то реализованы, кроме «бесконечной ленты», но сути это не меняет, паровозы и пароходы тоже реализованы.

Всё, что реализовано в физическом мире, является жалкими конечными автоматами. То есть в плане вычислительных возможностей кардинально уступает машине тюринга и её эквивалентам.

Это смахивает на демагогию. Можно взять в качестве вычислителя (черного ящика) просто человека который умеет читать и писать. Это не даст нам представления о природе вычислений. Если она невыразима, если это магия, то и не надо выдавать желаемое за действительное. А понимания природы вычислений это не дает. Это всего лишь ЯП.

как это не выразима? Вот тебе формализация, через нее выразимы вычисления. Что тебе надо еще? можешь китайца как формальность предложить. Никто ж не запрещает.

Из «человека, который умеет читать и писать» труднее вывести всякие закономерности и теории.

Не надо ему напоминать про конечный автомат. Он сейчас заладит - а что такое состояния? А как они реализованы? А кто их проверяет?

Я считаю претензии этих машин на формализацию вычислений необоснованными.
В них изнчально присутствует некоторый «интерфейс», а этого быть не должно, на мой взгляд.

Чего конкретно быть не должно, о каком «интерфейсе» ты мямлишь? МТ имеет совершенно формальное определение, в терминах конечных автоматов и теории множеств. Головка и лента — это всего лишь метафоры, позволяющие тебе сформировать наглядное представление о формальной конструкции.

МТ - это даже не идеальный газ. Это некая умозрительная модель, созданная для иллюстрации некоего математического принципа. Всё. К физическому миру она относится чуть менее, чем никак.

В плане вычислительных возможностей - да. Но в качестве формализации, это одно и тоже. Разница лишь в том, что на конечной ленте вычисление остановится с окончанием самой ленты.

Где я писал о какой-то связи с физическим миром? Я написал, что в качестве формальной модели она не годится.

Ты же сам в стартовом посте задался вопросами навроде «Как головка идентифицирует символ метки». Помоему, это и есть физическая реализуемость. Мне непонятно, зачем задавать такие вопросы (инженерные по сути), если ты не собрался эту машину строить у себя в гараже.

Нас интересуют вычисления на машине. А с китайцами занимаются психологи. Китаец - это готовая машина. А нам нужна реализация этого китайца (прошу воспринимать адекватно, как метафору, е-нно). В этом смысле МТ сосет.

Заодно докажи равную мощность магазинного автомата и конечного автомата. У ниж тоже разница всего лишь в «емкости ленты»

Ты тупишь. И сильно.

Но в качестве формализации, это одно и тоже.

У тебя в голове гуманитарный понос. Иди уже просветлись: http://en.wikipedia.org/wiki/Turing_machine#Formal_definition

Это называется недостатком интеллекта. У меня тоже такое было по перваку, когда формальные описания NP полных проблем изучал.

Да вот же, её можно и из лего собрать, правда лента конечная http://www.youtube.com/watch?v=FTSAiF9AHN4

Причем тут равная мощность? Смысл в том, что оба они конечны, и в этом смысле эквивалентны. Автомат годится для описания очереди выстрелов. В том числе и бесконечной.

Я пасс

Твоя тупость уходит в бесконечнось.

Не думаю, что изучив что-либо, можно что-либо понять. Это разные вещи.

Ты Турчина уже прочёл?

Уходи, толстенький.

Понятно, что тебя всегда устраивает то, что тебе объясняют. Поэтому смысла твоего пребывания втреде не вижу.

PS Неужели это хомячье действительно думает, что кто-то кроме них не способен найти статью и прочитать? Тоже загадка какая то. Может создам тему по этому поводу, вроде: «Поведенческие аномалии современного лемминга»