По поводу гладких многообразий. Да, деталей много, но они все разбираются в Boone, Haken, Poenaru "On Recursively Unsolvable Problems in Topology"

Если нужны только PL, то по аналогии можно запросить больше информации, чем просто триангуляция. Т.е. считать конечным копредставлением многообразия 1) симплициальный комплекс 2) и, например, еще комплекс для каждой вершины, который должен быть общим измельчением линка этой вершины и границы стандартного симплекса. Тут, в отличие от гладкого сучая, особых деталей нет, вроде все понятно.

Если нужно сделать именно триангуляцией, без дополнительной информации. То легче чуть видоизменить, то, что я предлагал раньше. Считать копредставлением PL-многообразия те комплексы, у которых все звезды вершин линейно (без дополнительных подразбиений) вкладываются в R^n (проверяется тем же Тарским-Сайденбергом). Если взять многообразие, подразбить звезды вершин чтобы они вкалдывались линейно (пересичения звед измельчать несколько раз), тогда у новых, появившихся от измельчения, вершин звезды уже тоже вкладываются. Вроде работает для компактных, не?

Но вообщето, если конечная цель это случайное 4-мерное многообразие, то эти методы плохо работают, потому что они слишком геометричны (ну как генерировать такие представления?), а в размерности 4 в отличие от 3 это плохо. Если цель - это случайная топология, а не случайная геометрия, то в размерности 4 я бы смотрел в сторону kirby calculus или trisections.