машина Тьюринга

Нужно также провести обратное сравнение: существуют ли вещи, которые может сделать обычный компьютер, а машина Тьюринга — нет.

We also need to consider the opposite comparison: are there things a common computer can do that a Turing machine cannot.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Тогда существует и некая машина Тьюринга Н, которая «решает», остановится ли в конце концов n-я машина Тьюринга, действуя на число т.

Then there must be some Turing machine H which 'decides' whether or not the with Turing machine, when acting on the number m, eventually stops.

Пенроуз, Роджер / Новый ум короля. О компьютерах, мышлении и законах физикиPenrose, Roger / The Emperor's New Mind. Concerning Computers, Minds, and The Laws of Physics

The Emperor's New Mind. Concerning Computers, Minds, and The Laws of Physics

Penrose, Roger

© Oxford University Press, 1989

Новый ум короля. О компьютерах, мышлении и законах физики

Пенроуз, Роджер

© Перевод на русский язык: Едиториал УРСС, 2002

© Oxford University Press, 1989

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

The Turing machine is required to start with an empty stack and implement the sequence of push and pop operations, as specified on the input, reading from left to right.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Запишите один из возможных кодов машины Тьюринга, изображенной на рис. 8.9.

Write one of the possible codes for the Turing machine of Fig. 8.9.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Построим машину Тьюринга и посмотрим, как она ведет себя на типичном входе.

Let us design a Turing machine and see how it behaves on a typical input.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

На все вопросы относительно конкретных значений разрешимого предиката Р (а) можно ответить с помощью подходящей абсолютной машины Тьюринга.

All the questions about particular values of a decidable predicate P(a) can be answered by a suitable absolute Turing machine.

Клини, С.К. / Математическая логикаKleene, Stephen Cole / Mathematical Logic

Mathematical Logic

Kleene, Stephen Cole

© 1967 by Stephen Cole Kleene

Математическая логика

Клини, С.К.

© Перевод на русский язык «Мир», 1973

Соглашения по обозначениям машин Тьюринга

Notational Conventions for Turing Machines

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Однако подобный подход приводит к медленной работе алгоритма ЦОС, так как микропроцессор и кристалл ЦСП попадают под определение машины Тьюринга.

However, this also results in the slowest performance for the DSP algorithm because microprocessor and DSP chips are both classed as Turing machines.

Максфилд, Клайв / Проектирование на ПЛИС. Архитектура, средства и методы. Курс молодого бойцаMaxfield, Clive / The design warrior's guide to FPGAs: Devices, Tools and Flows

The design warrior's guide to FPGAs: Devices, Tools and Flows

Maxfield, Clive

© 2004, Mentor Graphics Corporation and Xilinx, Inc.

Проектирование на ПЛИС. Архитектура, средства и методы. Курс молодого бойца

Максфилд, Клайв

© Издательский дом «Додэка-XXI», 2007

Наша следующая цель — разработать для машин Тьюринга такой код, чтобы всякую МТ с входным алфавитом {0, 1} можно было рассматривать как двоичную цепочку.

Our next goal is to devise a binary code for Turing machines so that each TM with input alphabet {0,1} may be thought of as a binary string.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Согласно теореме 9.11 все проблемы, связанные только с языками машин Тьюринга, неразрешимы.

All problems about Turing machines that involve only the language that the TM accepts are undecidable, by Theorem 9.11.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

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

Because of this polynomial equivalence, our conclusions about what a Turing machine can or cannot do with adequate efficiency apply equally well to a computer.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

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

Informally but clearly describe nondeterministic Turing machines — multitape if you like — that accept the following languages.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

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

In this section, we shall define a type of Turing machine that models the generation of random numbers and the use of those numbers in algorithms.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Рандомизированные алгоритмы и машины Тьюринга.

Randomized Algorithms and Turing Machines:

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001

Остается непонятным, что общего между рекурсивными функциями и машинами Тьюринга, которые всегда останавливаются.

Yet these recursive functions don't seem to have anything to do with Turing machines that always halt.

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри / Введение в теорию автоматов, языков и вычисленийHopcroft, John,Motwani, Rajeev,Ullman, Jeffrey / Introduction to automata theory, languages, and computation

Introduction to automata theory, languages, and computation

Hopcroft, John,Motwani, Rajeev,Ullman, Jeffrey

© 2001 by Addison-Wesley

Введение в теорию автоматов, языков и вычислений

Хопкрофт, Джон,Мотвани, Раджив,Ульман, Джеффри

© Издательский дом "Вильямс", 2002

© Addison-Wesley Publishing Company, Inc. 2001