ssmt-presentation-material (1005984), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

е. подсчет количества узлов, требуемых длярешения той или иной задачи (например, длятрансляции какого-либо формального языка).В то время, когда автор приступил к работе наднастоящей главой, были получены интересныерезультаты такого рода (отметим работы Ю. Хартманиса(J. Hartmanis) и Р. Э.

Стирнса (R. Е. Stearns)), но только дляспециальных классов {{машин Тьюринга с множествомлент и головок чтения/записи}}.3.063.07НА3.083.093.103.113.12НА3.13ОригиналThe Turing machine model iscomparatively unrealistic, so theseresults tended to have little to do withpractical problems.We must admit that, as the number n ofnodes created by a linking automatonapproaches infinity, we don't know howto build such a device physically, sincewe want the machine operations to takethe same amount of time regardless ofthe size of n; if {{linking}} is representedby using addresses as in a computermemory, it is necessary to put a boundon the number of nodes, since the linkfields have a fixed size.Статистическая СМПМодель машины Тьюринга сравнительнонереально, так что эти результаты какправило, имеют мало общего спрактическими проблемами.Мы должны признать, что, как число пузлов, созданных по Образцыбесконечности автомата подходы, мы незнаем, как построить такие устройствафизически, так как мы хотим машинныхопераций принять столько же времени,независимо от размера n, если {{Образцы}}представлены с помощью адресов, как впамяти компьютера, необходимо поставитьоценку числа узлов, так как ссылка поляимеют фиксированный размер.A {{multitape Turing machine}} istherefore a more realistic model when napproaches infinity.Yet it seems reasonable to believe thata {{linking automaton}} as describedabove leads to a more appropriatetheory of the complexity of algorithmsthan Turing machines do, even when{{asymptotic formulas}} for large n areconsidered, because the theory is morelikely to be relevant for practical valuesof n.Furthermore when n gets bigger than1030 or so, not even a {{one-tape Turingmachine}} is realistic: It could never bebuilt.Relevance is more important thanrealism.Many years have passed since theauthor wrote most of the commentsabove, and everybody can be glad thatsubstantial progress has indeed beenmade on the theory of linking automata(now called pointer machines).But of course much still remains to bedone.{{Тьюринга машина}} Поэтому болеереалистичной модели, когда N стремится кбесконечности.Однако, как представляется разумнымполагать, что {{связь автомата}}, какописано выше, приводит к болееподходящей теории сложности алгоритмов,чем машины Тьюринга делать, даже если{{асимптотические формулы}} прибольших п считаются, потому что теория,скорее всего, иметь отношение кпрактической значениях п.Кроме того, когда п становится больше, чем1030 или около того, даже не одна {{машинаТьюринга}} является реалистичной: онаникогда не может быть построен.Соответствие является более важным, чемреализм.Много лет прошло с тех пор автор написалбольшую часть комментарии выше, и всеможет быть рад, что существенный прогрессдействительно были сделаны на теорииОбразцы автоматов (сейчас он называетсяуказатель машин).Но, конечно, многое еще предстоит сделать.Трансфертная СМПМодель Машины Тьюринга сравнительнонереалистична, таким образом, этирезультаты имели тенденцию иметь малообщего с практическими проблемами.Мы должны признать, что, посколькуномер n узлов, создаваемыхсоединяющимся автоматом, приближается кбесконечности, мы не знаем, как создатьтакое устройство физически, так как мыхотим, чтобы машинные операции занялито же самое количество временинезависимо от размера n; если{{соединение}} представляется прииспользовании адресов как в памятикомпьютера, необходимо поместитьпривязанный число узлов, так как у полейссылки есть фиксированный размер.{{Машина Тьюринга мультиленты}} поэтому более реалистическая модель,когда n приближается к бесконечности.Все же кажется разумным полагать, что{{соединяющийся автомат}} как описановыше приводит к более соответствующейтеории сложности алгоритмов, чем МашиныТьюринга, даже когда {{асимптотическиеформулы}} для большого n рассматривают,потому что теория, более вероятно, будетважна для практических значений n.ПереводчикМодель машины Тьюринга сравнительно нереальна, апотому полученные результаты имеют мало общего срешением практических задач.Кроме того, когда n становится больше чемприблизительно 1030, не, даже {{МашинаТьюринга с одной лентой}} реалистична: Этоникогда не могло создаваться.Уместность более важна чем реализм.Кроме того, когда n становится больше, чем 1030 илиоколо того, даже {{одноленточная машина Тьюринга}}не является реалистичной: она никогда не будетпостроена.Принципы важнее реалий.Много лет передали, так как автор записалбольшинство комментариев выше, и всемогут радоваться, что значительный прогрессбыл действительно сделан на теориисоединения автоматов (теперь названныммашинами указателя).Но конечно много все еще остается бытьсделанным.Со времени первого написания автором большинстваприведенных выше комментариев утекло много воды,и можно порадоваться, что в теории связывающихавтоматов (сегодня называемых машинами указателей(pointer machines)) достигнут определенный прогресс,хотя, конечно же, предстоит еще немало сделать в этойобласти.14Следует признать, что при стремлении количествасозданных связывающим автоматом узлов n кбесконечности неизвестно, как построить такоеустройство физически, поскольку желательно, чтобыоперации машины выполнялись за одно и то же времянезависимо от размера n.Если {{связывание}} представлено с использованиемадресов в машинной памяти, необходимо определитьграницу для количества узлов, поскольку поля связейимеют фиксированный размер.{{Многоленточная машина Тьюринга}} поэтомупредставляет собой более реалистичную модель пристремлении n к бесконечности.Представляется также обоснованной уверенность в том,что описанные выше {{связывающие автоматы}}приведут к созданию более приемлемой теориисложности алгоритмов, чем машина Тьюринга, даже прирассмотрении {{асимптотических формул}} длябольших n, так как эта теория больше подходит дляпрактических значений n..

Характеристики

Список файлов ВКР